P4751 H’s problem(h)
时间: 1000ms / 空间: 655360KiB / Java类名: Main
背景
冬令营入学测试
描述
小H是一个喜欢逛街的女孩子，但是由于上了大学，DDL越来越多了，她不能一直都处于逛街的状态。为了让自己能够更加沉迷于学习，她规定一次逛街只逛T个单位的时间。
小H从1号店出发，从1号店走到第i号店需要花费ai的时间，这些店形成了一条直线，也就是说小H从第i号店走到第i+1号店需要花费的时间为a{i+1}-ai。若小H选择了第i号店并且进去逛，则会消耗bi的时间。对于第i家店，小H都对它有自己的看法。具体地，可以用ci来表示小H是否喜欢这家店。如果ci=1，则表示小H喜欢i号店，否则若ci=0，则表示小H不喜欢这家店。
小H想尽可能逛更多的店，但是她也有属于自己的目标，也就是说逛至少k家喜欢的店，在这个基础上，能逛的店越多越好。
小H现在想知道自己最多能逛多少店，当然若小H无论如何也逛不到k家喜欢的店，那么你输出-1就行了。
输入格式
第一行3个数n,T,k。
接下来一行n个数表示ai。
接下来一行n个数表示bi。
接下来一行n个数表示ci。
请在此填写输入格式
输出格式
输出一个数表示答案。
请在此填写输出格式
备注
输入样例
4 11 1
0 1 2 10
1 1 1 1
0 0 0 1
输出样例
1
数据范围
对于20%的数据n<=20。
对于40%的数据n<=1000。
对于100%的数据n<=100000，1<=T<=10^9，0<=k<=n，a1=0，a1<a2<…<an<=10^9，1<=bi<=10^9，0<=ci<=1，数据有梯度。
不知道为什么写错了不管了 我用的treap
标程动态开点的线段树也有的点TLE了....
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define lc t[x].l
#define rc t[x].r
const int N=1e5+5;
typedef long long ll;
int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
return x*f;
}
struct node{
int l,r,size,w,rnd;
ll sv,sum,v;
}t[N];
int sz,root;
inline void update(int x){
t[x].size=t[lc].size+t[rc].size+t[x].w;
t[x].sum=t[lc].sum+t[rc].sum+t[x].sv;
}
inline void lturn(int &x){
int c=rc;rc=t[c].l;t[c].l=x;
update(x);update(c);x=c;
}
inline void rturn(int &x){
int c=lc;lc=t[c].r;t[c].r=x;
update(x);update(c);x=c;
}
void ins(int &x,int v){
if(!x){
x=++sz;
t[x].v=t[x].sv=t[x].sum=v;
t[x].rnd=rand();t[x].l=t[sz].r=0;
t[x].w=t[x].size=1;
return;
}
t[x].size++;t[x].sum+=v;
if(v==t[x].v) {t[x].w++;t[x].sv+=t[x].v;}
else if(v<t[x].v){
ins(lc,v);
if(t[lc].rnd<t[x].rnd) rturn(x);
}else{
ins(rc,v);
if(t[rc].rnd<t[x].rnd) lturn(x);
}
}
void print(int x){
if(lc) print(lc);
printf("tree %d %d %d %d %d %d\n",x,t[x].v,t[x].sv,t[x].sum,t[x].size,t[x].w);
if(rc) print(rc);
}
inline ll que(int x,ll k){
if(x==0) return 0;
if(k<=t[lc].sum) return que(lc,k);
else if(k<=t[lc].sum+t[x].sv){
return t[lc].size+(k-t[lc].sum)/t[x].v;
}return t[lc].size+t[x].w+que(rc,k-t[lc].sum-t[x].sv);
}
int n,T,k,a[N],b[N],c[N],ans=-1;
priority_queue<int,vector<int>,greater<int> > q;
void solve(){
for(int i=1;i<=n;i++){
if(c[i]==1){
q.push(b[i]); T-=b[i];
if(q.size()>k){
int _=q.top();q.pop();T+=_;
ins(root,_);
}
}else ins(root,b[i]);
//printf("hi %d %d %d %d\n",i,a[i],ans,que(root,T-a[i]));
if(q.size()==k&&T-a[i]>=0) ans=max((ll)ans,k+que(root,T-a[i]));
}
//print(root);
printf("%d",ans);
}
int main(){
n=read();T=read();k=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
for(int i=1;i<=n;i++) c[i]=read();
solve();
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
ll ans=0;
char last=' ',ch=getchar();
while(ch<'0' || ch>'9')last=ch,ch=getchar();
while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
//head
#define M 5000000
#define N 110000
ll T,sum1[M];
int sum2[M],lson[M],rson[M],k,kk,n,a[N],b[N],c[N],num,sum,ans,root;
void add(int &u,int l,int r,int x){
if(!u){
u=++num;
sum1[u]=sum2[u]=lson[u]=rson[u]=0;
}
sum1[u]+=x;sum2[u]++;
if(l==r)return;
int mid=(l+r)/2;
if(x<=mid) add(lson[u],l,mid,x);
else add(rson[u],mid+1,r,x);
}
int find(int u,int l,int r,int t){
if(!u)return r;
if(sum1[u]<=t){sum+=sum2[u];return r;}
if(l==r){
return r-1;
}
int mid=(l+r)/2;
if(sum1[lson[u]]<=t){
sum+=sum2[lson[u]];
return find(rson[u],mid+1,r,t-sum1[lson[u]]);
}
else return find(lson[u],l,mid,t);
}
int find2(int u,int l,int r,int t){
if(!u || sum2[u]==0)return 0;
if(l==r)return l;
int mid=(l+r)/2;
if(t<=mid){
int tt=find2(lson[u],l,mid,t);
if(tt)return tt;
}
find2(rson[u],mid+1,r,t);
return 0;
}
ll Sum(int u,int l,int r,int x){
if(!u)return 0;
if(x<l)return 0;
if(x>=r)return sum1[u];
int mid=(l+r)/2;
return Sum(lson[u],l,mid,x)+Sum(rson[u],mid+1,r,x);
}
int d[N];
priority_queue<int> q1;
int main(){
//freopen("h10.in","r",stdin);
//freopen("h10.out","w",stdout);
// freopen("55.out","w",stdout);
n=read();T=read();kk=k=read();
rep(i,1,n)a[i]=read();
rep(i,1,n)b[i]=d[i]=read();
rep(i,1,n)c[i]=read();
sort(d+1,d+n+1);
ll ss=0;
// rep(i,1,30)ss+=d[i];
ans=-1;
rep(i,1,n){
// cout<<i<<endl;
T-=a[i]-a[i-1];
if(c[i]){
k--;
q1.push(b[i]);
T-=b[i];
if(k<0){
int tt=q1.top();
T+=tt;
q1.pop();
++k;
add(root,1,1000000000,tt);
}
}
else add(root,1,1000000000,b[i]);
if(k==0 && T>=0){
sum=0;
int t=find(root,1,1000000000,T);
if(sum1[root]>T){
int t2=find2(root,1,1000000000,t+1);
if(t2)sum+=(T-Sum(root,1,1000000000,t))/t2;
}
ans=max(ans,sum+kk);
}
}
cout<<ans<<endl;
return 0;
}