Submission #435492

#	Time	Username	Problem	Language	Result	Execution time	Memory
435492		errorgorn	Distributing Candies (IOI21_candies)	C++17	100 / 100	1857 ms	40880 KiB

candies

#include "candies.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
struct node{ //range sum updates, range max and min queries
	int s,e,m;
	ll mn=0,mx=0,lazy=0;
	node *l,*r;
 
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
 
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
 
	void propo(){
		if (lazy){
			mn+=lazy;
			mx+=lazy;
 
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			lazy=0;
		}
	}
 
	void update(int i,int j,ll k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
 
			l->propo(),r->propo();
			mn=min(l->mn,r->mn);
			mx=max(l->mx,r->mx);
		}
	}
 
	ll query_mn(int i,int j){
		propo();
 
		if (s==i && e==j) return mn;
		else if (j<=m) return l->query_mn(i,j);
		else if (m<i) return r->query_mn(i,j);
		else return min(l->query_mn(i,m),r->query_mn(m+1,j));
	}
 
	ll query_mx(int i,int j){
		propo();
 
		if (s==i && e==j) return mx;
		else if (j<=m) return l->query_mx(i,j);
		else if (m<i) return r->query_mx(i,j);
		else return max(l->query_mx(i,m),r->query_mx(m+1,j));
	}
} *root=new node(0,200005);
 
struct upd{
	int pos;
	int ct;
	ll val;
};
 
int n,q;
int cap[200005];
vector<upd> u;
 
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n=sz(c),q=sz(l);
    rep(x,0,n) cap[x]=c[x];
 
    rep(x,0,q){
		u.pub(upd({l[x],x+2,v[x]}));
		u.pub(upd({r[x]+1,x+2,-v[x]}));
	}
 
	sort(all(u),[](upd i,upd j){
		return i.pos>j.pos;
	});
 
	root->update(0,0,1e18);
 
	vector<int> ans;
 
	rep(x,0,n){
		while (!u.empty() && u.back().pos==x){
			root->update(u.back().ct,200005,u.back().val);
			u.pob();
		}
 
		//cout<<x<<": "; rep(x,0,5) cout<<root->query_mn(x,x)<<" "; cout<<endl;
		//cout<<"cap: "<<cap[x]<<endl;
 
		int lo=0,hi=200005,mi;
		while (hi-lo>1){
			mi=hi+lo>>1;
 
			if (root->query_mx(mi,200005)-root->query_mn(mi,200005)>cap[x]) lo=mi;
			else hi=mi;
		}
 
		//cout<<lo<<" "<<hi<<endl;
 
		if (root->query_mn(lo,lo)==root->query_mn(lo,200005)){
			//cout<<"hit max"<<endl;
			ans.pub(cap[x]-(root->query_mx(hi,200005)-root->query_mx(200005,200005)));
		}
		else{
			//cout<<"hit min"<<endl;
			ans.pub(root->query_mn(200005,200005)-root->query_mn(hi,200005));
		}
 
	}
 
	return ans;
}

Compilation message (stderr)

candies.cpp: In constructor 'node::node(int, int)':
candies.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:123:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |    mi=hi+lo>>1;
      |       ~~^~~

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