Submission #444614

#	Time	Username	Problem	Language	Result	Execution time	Memory
444614		KLPP	Distributing Candies (IOI21_candies)	C++17	29 / 100	327 ms	26968 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>

using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
#define INF 1000000000000000000LL
lld arr[1000000];
struct f{
	lld A; lld B; lld C;
};
f nest(f alpha, f beta){
	return f{min(alpha.A,max(beta.A+alpha.C,alpha.B)),max(beta.B+alpha.C,alpha.B),alpha.C+beta.C};
}
/*
f max(f a, f b){
	
};
f in(f a, f b){
	
};
f operator +(f a, f b){
	
};
struct g{
	f A,B,C;
};*/

class ST{
	f lazy[1000000];
	public:
	void build(int a, int b, int node){
		lazy[node]=f{INF,-INF,0};
		if(a==b)return;
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
	}
	void propag(int a, int b, int node){
		lazy[2*node]=nest(lazy[node],lazy[2*node]);
		lazy[2*node+1]=nest(lazy[node],lazy[2*node+1]);
		lazy[node]=f{INF,-INF,0};
	}
	void update(int a, int b, int node, int x, int y, f operation){
		if(b<x || y<a)return;
		if(x<=a && b<=y){
			lazy[node]=nest(operation,lazy[node]);
			return;
		}
		propag(a,b,node);
		int mid=(a+b)/2;
		update(a,mid,2*node,x,y,operation);
		update(mid+1,b,2*node+1,x,y,operation);
	}
	lld query(int a, int b, int node, int pos){
		if(pos<=a && b<=pos){
			return min(lazy[node].A,max(lazy[node].B,lazy[node].C));
		}
		propag(a,b,node);
		int mid=(a+b)/2;
		if(mid<pos)return query(mid+1,b,2*node+1,pos);
		if(mid>=pos)return query(a,mid,2*node,pos);
	}
	f query2(int a, int b, int node, int pos){
		if(pos<=a && b<=pos){
			return lazy[node];
		}
		propag(a,b,node);
		int mid=(a+b)/2;
		if(mid<pos)return query2(mid+1,b,2*node+1,pos);
		if(mid>=pos)return query2(a,mid,2*node,pos);
	}
	void print(int a, int b, int node){
		cout<<a<<" "<<b<<" "<<node<<" "<<lazy[node].A<<" "<<lazy[node].B<<" "<<lazy[node].C<<endl;
		if(a==b)return;
		int mid=(a+b)/2;
		print(a,mid,2*node);
		print(mid+1,b,2*node+1);
	}
};
ST S;
vector<int> a,b;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    std::vector<int> s(n);
    /*if(n<=2000 && l.size()<=2000){
		    rep(i,0,n)arr[i]=0;
    rep(q,0,l.size()){
		rep(i,l[q],r[q]+1){
			if(v[q]>0){
				arr[i]=min(arr[i]+v[q],(lld)c[i]);
			}else{
				arr[i]=max(arr[i]+v[q],0LL);
			}
		}
	}
	rep(i,0,n)s[i]=arr[i];
	return s;
	}*/
    /*rep(i,0,n+1)arr[i]=0;
    rep(i,0,l.size()){
		arr[l[i]]+=v[i];
		arr[r[i]+1]-=v[i];
	}
	rep(i,1,n)arr[i]=arr[i]+(arr[i-1]);
	rep(i,0,n){
		s[i]=min(arr[i],(lld)c[i]);
	}*/
    a.resize(n);
    b.resize(n);
    S.build(0,l.size(),1);
    S.update(0,l.size(),1,0,0,f{INF,0,-INF});
    rep(i,1,l.size()+1){
		//S.print(0,n-1,1);
		if(v[i-1]>0){
			S.update(0,l.size(),1,0,i-1,f{INF,-INF,v[i-1]});
			S.update(0,l.size(),1,i,i,f{INF,-INF,0});
		}
		if(v[i-1]<0){
			S.update(0,l.size(),1,0,i,f{INF,-INF,v[i-1]});
			S.update(0,l.size(),1,0,i,f{INF,0,0});
		}
		//S.print(0,l.size(),1);
	}
	vector<pair<lld,lld> >V;
    rep(i,0,l.size()+1){
		if(i==0 || v[i-1]>0){
			//cout<<S.query2(0,l.size(),1,i).B<<" "<<S.query2(0,l.size(),1,i).C<<endl;
			V.push_back({S.query2(0,l.size(),1,i).B,S.query2(0,l.size(),1,i).C});
		}
	}
	//rep(i,0,V.size())cout<<V[i].first<<" "<<V[i].second<<endl;
	sort(V.begin(),V.end());
	vector<pair<lld,lld> >V2;
	V2.push_back(V[0]);
	rep(i,1,V.size()){
		if(V[i].second<V2[V2.size()-1].second){
			V2.push_back(V[i]);
		}
	}
	//rep(i,0,V2.size())cout<<V2[i].first<<" "<<V2[i].second<<endl;
	rep(i,0,n){
		int lo=0;
		int hi=V2.size()-1;
		while(hi-lo>1){
			int mid=(hi+lo)/2;
			if(V2[mid].first<V2[mid].second+c[i]){
				lo=mid;
			}else hi=mid;
		}
		//cout<<max(V2[lo].first,V2[lo].second+c[i])<<" "<<max(V2[hi].first,V2[hi].second+c[i])<<endl;
		s[i]=min(max(V2[lo].first,V2[lo].second+c[i]),max(V2[hi].first,V2[hi].second+c[i]));
	}
    return s;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:5:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,a,b) for(int i=a;i<b;i++)
......
  115 |     rep(i,1,l.size()+1){
      |         ~~~~~~~~~~~~~~           
candies.cpp:115:5: note: in expansion of macro 'rep'
  115 |     rep(i,1,l.size()+1){
      |     ^~~
candies.cpp:5:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,a,b) for(int i=a;i<b;i++)
......
  128 |     rep(i,0,l.size()+1){
      |         ~~~~~~~~~~~~~~           
candies.cpp:128:5: note: in expansion of macro 'rep'
  128 |     rep(i,0,l.size()+1){
      |     ^~~
candies.cpp:5:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,a,b) for(int i=a;i<b;i++)
......
  138 |  rep(i,1,V.size()){
      |      ~~~~~~~~~~~~                
candies.cpp:138:2: note: in expansion of macro 'rep'
  138 |  rep(i,1,V.size()){
      |  ^~~
candies.cpp: In member function 'f ST::query2(int, int, int, int)':
candies.cpp:73:2: warning: control reaches end of non-void function [-Wreturn-type]
   73 |  }
      |  ^

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33