Submission #435302

#TimeUsernameProblemLanguageResultExecution timeMemory
435302NicolaAbusaad2014Distributing Candies (IOI21_candies)C++17
29 / 100
242 ms21928 KiB
/** * Prof.Nicola **/ #include <bits/stdc++.h> #include "candies.h" using namespace std; #define endl "\n" #define mp make_pair #define F first #define S second #define REP(i,l,r) for(long long i=(l);i<(r);i++) #define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--) const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1}; const long double pi=3.14159265359; const long long mod=1e9+7; long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;} template<class T>void re(T&x){cin>>x;} template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);} template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}} template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}} template<class T>void out(T x){cout<<x<<" ";} template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;} template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;} template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;} template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();} template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();} long q; struct segment_tree1 { vector<long long>tree; long long operation(long long x,long long z) { return max(x,z); } void build(vector<long long>v) { tree.clear(); long long x=v.size(); while(x&(x-1)){ x=x&(x-1); } if(v.size()!=x){ x*=2; } tree.resize(x*2); tree[0]=x; for(long i=0;i<v.size();i++){ tree[i+x]=v[i]; } for(long i=x-1;i>0;i--){ tree[i]=operation(tree[i*2],tree[(i*2)+1]); } } long long get(long long l,long long r) { l+=tree[0]; r+=tree[0]; long long ans=0; while(l<=r){ if(l%2==1){ ans=operation(ans,tree[l]); } if(r%2==0){ ans=operation(ans,tree[r]); } l++; l/=2; r--; r/=2; } return ans; } void update(long long x,long long z) { x+=tree[0]; tree[x]=z; x/=2; while(x>0){ tree[x]=operation(tree[x*2],tree[(x*2)+1]); x/=2; } } }; struct segment_tree2 { vector<long long>tree; long long operation(long long x,long long z) { return min(x,z); } void build(vector<long long>v) { tree.clear(); long long x=v.size(); while(x&(x-1)){ x=x&(x-1); } if(v.size()!=x){ x*=2; } tree.resize(x*2); tree[0]=x; for(long i=0;i<v.size();i++){ tree[i+x]=v[i]; } for(long i=x-1;i>0;i--){ tree[i]=operation(tree[i*2],tree[(i*2)+1]); } } long long get(long long l,long long r) { l+=tree[0]; r+=tree[0]; long long ans=1e9; while(l<=r){ if(l%2==1){ ans=operation(ans,tree[l]); } if(r%2==0){ ans=operation(ans,tree[r]); } l++; l/=2; r--; r/=2; } return ans; } void update(long long x,long long z) { x+=tree[0]; tree[x]=z; x/=2; while(x>0){ tree[x]=operation(tree[x*2],tree[(x*2)+1]); x/=2; } } }; segment_tree1 a; segment_tree2 b; long mx(long x) { long l=x,r=q-1,mid; while(l<r){ mid=(l+r)/2; if(a.get(l,mid)<=a.get(mid+1,r)){ l=mid+1; } else{ r=mid; } } return l; } long mn(long x) { long l=x,r=q-1,mid; while(l<r){ mid=(l+r)/2; if(b.get(l,mid)>=b.get(mid+1,r)){ l=mid+1; } else{ r=mid; } } return l; } 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(); q=v.size(); std::vector<int> s(n); long long now=0,sub=0,p1,p2,x=0; vector<pair<long long,long> >srtd(n); REP(i,0,n){ srtd[i]=mp(c[i],i); } sort(srtd.rbegin(),srtd.rend()); vector<long long>sum(q); REP(i,0,q){ x+=v[i]; x=min(x,(long long)srtd[0].first); x=max(0ll,x); sum[i]=x; } a.build(sum); b.build(sum); x=0; while(now<n&&x<q){ while(now<n&&x<q){ p1=mx(x); p2=mn(p1); while(now<n&&sum[p1]-sub<=srtd[now].first){ s[srtd[now].second]=sum[q-1]-sub; now++; } if(now>=n){ break; } sub+=min(sum[p1]-sub-srtd[now].first,sum[p2]-sub); if(sum[p2]-sub==0){ x=p2+1; } else{ break; } } if(now<n){ s[srtd[now].second]=sum[q-1]-sub; } now++; } return s; }

Compilation message (stderr)

candies.cpp: In member function 'void segment_tree1::build(std::vector<long long int>)':
candies.cpp:42:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   42 |         if(v.size()!=x){
      |            ~~~~~~~~^~~
candies.cpp:47:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(long i=0;i<v.size();i++){
      |                      ~^~~~~~~~~
candies.cpp: In member function 'void segment_tree2::build(std::vector<long long int>)':
candies.cpp:98:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   98 |         if(v.size()!=x){
      |            ~~~~~~~~^~~
candies.cpp:103:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(long i=0;i<v.size();i++){
      |                      ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...