oj.uz

Submission #435492

# Submission time Handle Problem Language Result Execution time Memory
435492 2021-06-23T11:28:22 Z errorgorn Distributing Candies (IOI21_candies) C++17
100 / 100
 1857 ms 40880 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25284 KB Output is correct
2 Correct 26 ms 25316 KB Output is correct
3 Correct 30 ms 25460 KB Output is correct
4 Correct 26 ms 25464 KB Output is correct
5 Correct 36 ms 25548 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1698 ms 40700 KB Output is correct
2 Correct 1809 ms 40676 KB Output is correct
3 Correct 1857 ms 40752 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 25292 KB Output is correct
2 Correct 641 ms 38432 KB Output is correct
3 Correct 932 ms 29884 KB Output is correct
4 Correct 1566 ms 40752 KB Output is correct
5 Correct 1562 ms 40712 KB Output is correct
6 Correct 1526 ms 40732 KB Output is correct
7 Correct 1611 ms 40748 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 25284 KB Output is correct
2 Correct 26 ms 25292 KB Output is correct
3 Correct 210 ms 38324 KB Output is correct
4 Correct 915 ms 28988 KB Output is correct
5 Correct 1141 ms 40704 KB Output is correct
6 Correct 1095 ms 40748 KB Output is correct
7 Correct 959 ms 40764 KB Output is correct
8 Correct 1083 ms 40716 KB Output is correct
9 Correct 1079 ms 40756 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25284 KB Output is correct
2 Correct 26 ms 25316 KB Output is correct
3 Correct 30 ms 25460 KB Output is correct
4 Correct 26 ms 25464 KB Output is correct
5 Correct 36 ms 25548 KB Output is correct
6 Correct 1698 ms 40700 KB Output is correct
7 Correct 1809 ms 40676 KB Output is correct
8 Correct 1857 ms 40752 KB Output is correct
9 Correct 33 ms 25292 KB Output is correct
10 Correct 641 ms 38432 KB Output is correct
11 Correct 932 ms 29884 KB Output is correct
12 Correct 1566 ms 40752 KB Output is correct
13 Correct 1562 ms 40712 KB Output is correct
14 Correct 1526 ms 40732 KB Output is correct
15 Correct 1611 ms 40748 KB Output is correct
16 Correct 23 ms 25284 KB Output is correct
17 Correct 26 ms 25292 KB Output is correct
18 Correct 210 ms 38324 KB Output is correct
19 Correct 915 ms 28988 KB Output is correct
20 Correct 1141 ms 40704 KB Output is correct
21 Correct 1095 ms 40748 KB Output is correct
22 Correct 959 ms 40764 KB Output is correct
23 Correct 1083 ms 40716 KB Output is correct
24 Correct 1079 ms 40756 KB Output is correct
25 Correct 23 ms 25240 KB Output is correct
26 Correct 903 ms 28948 KB Output is correct
27 Correct 674 ms 38328 KB Output is correct
28 Correct 1663 ms 40712 KB Output is correct
29 Correct 1637 ms 40700 KB Output is correct
30 Correct 1680 ms 40752 KB Output is correct
31 Correct 1561 ms 40880 KB Output is correct
32 Correct 1511 ms 40748 KB Output is correct