oj.uz

Submission #1053293

# Submission time Handle Problem Language Result Execution time Memory
1053293 2024-08-11T10:19:13 Z epicci23 Distributing Candies (IOI21_candies) C++17
40 / 100
 375 ms 25276 KB 
#include "bits/stdc++.h"
#include "candies.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const long long INF = 1e18;

struct SegT_Min{
  int n;
  vector<long long> t;
  SegT_Min(int nn){
   n=nn;
   t.assign(4*n+5,INF);
  }
  void upd(int rt,int l,int r,int ind,long long u){
  	if(r<ind || l>ind) return;
  	if(l==r){
  	  t[rt]=min(t[rt],u);
  	  return;
  	}
  	int m=(l+r)/2;
  	upd(rt*2,l,m,ind,u),upd(rt*2+1,m+1,r,ind,u);
  	t[rt]=min(t[rt*2],t[rt*2+1]);
  }
  long long query(int rt,int l,int r,int gl,int gr){
  	if(r<gl || l>gr) return INF;
  	if(l>=gl && r<=gr) return t[rt];
  	int m=(l+r)/2;
  	return min(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
  }
};

struct SegT_Max{
  int n;
  vector<long long> t;
  SegT_Max(int nn){
   n=nn;
   t.assign(4*n+5,-INF);
  }
  void upd(int rt,int l,int r,int ind,long long u){
  	if(r<ind || l>ind) return;
  	if(l==r){
  	  t[rt]=max(t[rt],u);
  	  return;
  	}
  	int m=(l+r)/2;
  	upd(rt*2,l,m,ind,u),upd(rt*2+1,m+1,r,ind,u);
  	t[rt]=max(t[rt*2],t[rt*2+1]);
  }
  long long query(int rt,int l,int r,int gl,int gr){
  	if(r<gl || l>gr) return -INF;
  	if(l>=gl && r<=gr) return t[rt];
  	int m=(l+r)/2;
  	return max(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
  }
};

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int n=sz(C),q=sz(V);
    vector<int> ans(n);
    if(n<=2000 && q<=2000){
      for(int i=0;i<q;i++){
      	for(int j=L[i];j<=R[i];j++){
      	  ans[j]+=V[i];
      	  ans[j]=min(ans[j],C[j]);
      	  ans[j]=max(0,ans[j]);	
      	}
      }
      return ans;	
    }
    if(*min_element(all(V))>=0){
      vector<long long> amk(n);
      for(int i=0;i<q;i++){
      	amk[L[i]]+=V[i];
      	if(R[i]+1<n) amk[R[i]+1]-=V[i];
      }
      for(int i=1;i<n;i++) amk[i]+=amk[i-1];
      for(int i=0;i<n;i++) ans[i]=(int)min(amk[i],(long long)C[i]);
      return ans;	
    }
    vector<array<long long,2>> c;
    for(int i=0;i<n;i++) c.push_back({C[i],i});
    sort(all(c));
    long long pre[q+5];
    pre[0]=0;
    for(int i=1;i<=q;i++) pre[i]=pre[i-1]+V[i-1];
    SegT_Min t1(q);SegT_Max t2(q);
    for(int i=0;i<=q;i++){
     t1.upd(1,1,q,i,pre[i]);
     t2.upd(1,1,q,i,pre[i]);
    }

    long long p=0,cur=0;
  for(int i=n-1;i>=0;i--){
  	long long cap=c[i][0];
  	cur=min(cur,cap);
  	while(p<q){
	    int l=p+1,r=q+1;
	    while(l<r){
	      int m=(l+r)/2;
	      if(t1.query(1,1,q,p+1,m)<=pre[p]-cur) r=m;
	      else l=m+1;
	    }
	    int ans0=l;
	    l=p+1,r=q+1;
	    while(l<r){
	     int m=(l+r)/2;
	     if(t2.query(1,1,q,p+1,m)>=cap-cur+pre[p]) r=m;
	     else l=m+1;
	    }
	    int ansm=l;
	    if(ansm==q+1 && ans0==q+1) break;
	    p=min(ansm,ans0);
	    if(ans0<=ansm) cur=0;
	    else cur=cap;
    }
    ans[c[i][1]]=cur+pre[q]-pre[p];
  }
  return ans;
}

/*void _(){
  int n,q;
  cin >> n >> q;
  vector<array<int,2>> c;
  for(int i=1;i<=n;i++){
  	int a;cin >> a;
  	c.push_back({a,i});
  }
  int xd[q+5],ans[n+5],pre[q+5];
  pre[0]=0;
  for(int i=1;i<=q;i++){
  	cin >> xd[i];
    pre[i]=pre[i-1]+xd[i];
  }
  sort(all(c));
  SegT_Min t1(q);SegT_Max t2(q);
  for(int i=0;i<=q;i++){
    t1.upd(1,1,q,i,pre[i]);
    t2.upd(1,1,q,i,pre[i]);
  }

  int p=0,cur=0;
  for(int i=n-1;i>=0;i--){
  	int cap=c[i][0];
  	cur=min(cur,cap);
  	while(p<q){
	    int l=p+1,r=q+1;
	    while(l<r){
	      int m=(l+r)/2;
	      if(t1.query(1,1,q,p+1,m)<=pre[p]-cur) r=m;
	      else l=m+1;
	    }
	    int ans0=l;
	    l=p+1,r=q+1;
	    while(l<r){
	     int m=(l+r)/2;
	     if(t2.query(1,1,q,p+1,m)>=cap-cur-pre[p]) r=m;
	     else l=m+1;
	    }
	    int ansm=l;
	    if(ansm==q+1 && ans0==q+1) break;
	    p=min(ansm,ans0);
	    if(ans0<=ansm) cur=0;
	    else cur=cap;
    }
    ans[c[i][1]]=cur+pre[q]-pre[p];
  }

  for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i==n];
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9044 KB Output is correct
2 Correct 52 ms 12892 KB Output is correct
3 Correct 52 ms 12884 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 64 ms 19308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 63 ms 19308 KB Output is correct
4 Correct 84 ms 7996 KB Output is correct
5 Correct 322 ms 24764 KB Output is correct
6 Correct 256 ms 25276 KB Output is correct
7 Correct 159 ms 25276 KB Output is correct
8 Correct 375 ms 24768 KB Output is correct
9 Correct 51 ms 9040 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 65 ms 9044 KB Output is correct
7 Correct 52 ms 12892 KB Output is correct
8 Correct 52 ms 12884 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 64 ms 19308 KB Output isn't correct
11 Halted 0 ms 0 KB -