oj.uz

Submission #436968

# Submission time Handle Problem Language Result Execution time Memory
436968 2021-06-25T12:04:47 Z haojiandan Distributing Candies (IOI21_candies) C++17
100 / 100
 1258 ms 32316 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
typedef long long ll;
const ll INF=1e18;
const int maxn=(2e5)+10;
int n,q,c[maxn];
vector<pair<int,int> > Q[maxn];
ll mn[maxn*4],mx[maxn*4],lazy[maxn*4];
void puttag(int root,ll delta) {
	lazy[root]+=delta,mn[root]+=delta,mx[root]+=delta;
}
void pushdown(int root) {
	if (lazy[root]) {
		puttag(root<<1,lazy[root]),puttag(root<<1|1,lazy[root]); lazy[root]=0;
	}
}
void update(int L,int R,int l,int r,int root,ll delta) {
	if (L<=l&&r<=R) { puttag(root,delta); return; }
	int mid=(l+r)>>1; pushdown(root);
	if (L<=mid) update(L,R,l,mid,root<<1,delta);
	if (mid<R) update(L,R,mid+1,r,root<<1|1,delta);
	mn[root]=min(mn[root<<1],mn[root<<1|1]);
	mx[root]=max(mx[root<<1],mx[root<<1|1]);
}
pair<ll,ll> operator + (pair<ll,ll> t1,pair<ll,ll> t2) { return MP(min(t1.first,t2.first),max(t1.second,t2.second)); }
pair<ll,ll> query(int L,int R,int l,int r,int root) {
	if (L<=l&&r<=R) return MP(mn[root],mx[root]);
	int mid=(l+r)>>1; pushdown(root); pair<ll,ll> res=MP(INF,-INF);
	if (L<=mid) res=res+query(L,R,l,mid,root<<1);
	if (mid<R) res=res+query(L,R,mid+1,r,root<<1|1);
	return res;
}
vector<int> distribute_candies(vector<int> C, vector<int> l,vector<int> r, vector<int> v) {
	n=(int)C.size(); q=(int)v.size();
	for (int i=0;i<q;i++) l[i]++,r[i]++,Q[l[i]].push_back(MP(i+1,v[i])),Q[r[i]+1].push_back(MP(i+1,-v[i]));
	for (int i=1;i<=n;i++) c[i]=C[i-1];
	vector<int> ans(n);
	ll s=0;
	for (int i=1;i<=n;i++) {
		for (pair<int,int> A : Q[i]) update(A.first,q,1,q,1,A.second),s+=A.second;
		int l=1,r=q,mid;
		while (l<r) {
			mid=(l+r+1)>>1;
			pair<ll,ll> tmp=query(mid,q,1,q,1);
			if (tmp.second-tmp.first>=c[i]) l=mid; else r=mid-1;
		}
		pair<ll,ll> tmp=query(l,q,1,q,1);
		if (tmp.second-tmp.first>=c[i]) {
			pair<ll,ll> t2=query(l,l,1,q,1);
			if (tmp.first==t2.first) ans[i-1]=s-tmp.second+c[i]; else ans[i-1]=s-tmp.first;
		} else if (tmp.second>=c[i]) ans[i-1]=s-tmp.second+c[i];
		else if (tmp.first<0) ans[i-1]=s-tmp.first;
		else ans[i-1]=s;
	}
	return ans;
	
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 8 ms 5252 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1258 ms 32180 KB Output is correct
2 Correct 1179 ms 32276 KB Output is correct
3 Correct 1194 ms 32176 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4940 KB Output is correct
2 Correct 332 ms 26560 KB Output is correct
3 Correct 252 ms 9476 KB Output is correct
4 Correct 1041 ms 32188 KB Output is correct
5 Correct 1079 ms 32220 KB Output is correct
6 Correct 1214 ms 32196 KB Output is correct
7 Correct 1048 ms 32184 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 151 ms 25308 KB Output is correct
4 Correct 229 ms 8460 KB Output is correct
5 Correct 655 ms 28304 KB Output is correct
6 Correct 624 ms 28300 KB Output is correct
7 Correct 675 ms 28328 KB Output is correct
8 Correct 630 ms 28300 KB Output is correct
9 Correct 813 ms 28304 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 8 ms 5252 KB Output is correct
6 Correct 1258 ms 32180 KB Output is correct
7 Correct 1179 ms 32276 KB Output is correct
8 Correct 1194 ms 32176 KB Output is correct
9 Correct 7 ms 4940 KB Output is correct
10 Correct 332 ms 26560 KB Output is correct
11 Correct 252 ms 9476 KB Output is correct
12 Correct 1041 ms 32188 KB Output is correct
13 Correct 1079 ms 32220 KB Output is correct
14 Correct 1214 ms 32196 KB Output is correct
15 Correct 1048 ms 32184 KB Output is correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 4940 KB Output is correct
18 Correct 151 ms 25308 KB Output is correct
19 Correct 229 ms 8460 KB Output is correct
20 Correct 655 ms 28304 KB Output is correct
21 Correct 624 ms 28300 KB Output is correct
22 Correct 675 ms 28328 KB Output is correct
23 Correct 630 ms 28300 KB Output is correct
24 Correct 813 ms 28304 KB Output is correct
25 Correct 4 ms 4940 KB Output is correct
26 Correct 237 ms 8408 KB Output is correct
27 Correct 377 ms 26504 KB Output is correct
28 Correct 1080 ms 32316 KB Output is correct
29 Correct 1040 ms 32068 KB Output is correct
30 Correct 1098 ms 32160 KB Output is correct
31 Correct 1198 ms 32188 KB Output is correct
32 Correct 1065 ms 32176 KB Output is correct