oj.uz

Submission #482976

# Submission time Handle Problem Language Result Execution time Memory
482976 2021-10-27T08:29:40 Z MilosMilutinovic Distributing Candies (IOI21_candies) C++17
100 / 100
 364 ms 49404 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=201000;
int n,q;
VI qs2[N];
vector<PII> qs[N];
ll pref4[N],mn[N],mx[N];
struct node{
	ll val,mn,mx;
	node() {mn=mx=val=0;}
}nd[4*N];
void upd(int p) {
	nd[p].val=nd[p*2].val+nd[p*2+1].val;
	nd[p].mn=min(nd[p*2].mn,nd[2*p].val+nd[p*2+1].mn);
	nd[p].mx=max(nd[p*2].mx,nd[2*p].val+nd[p*2+1].mx);
}
void modify(int p,int l,int r,int tl,int x) {
	if (l==r) {
		nd[p].val+=x;
		nd[p].mx=nd[p].val;
		nd[p].mn=nd[p].val;
	} else {
		int md=(l+r)>>1;
		if (tl<=md) modify(p*2,l,md,tl,x);
		else modify(p*2+1,md+1,r,tl,x);
		upd(p);
	}
}
int get(int p,int l,int r,int c) {
	if (l==r) return max(0LL,min((ll)c,nd[p].val));
	int md=(l+r)>>1;
	if (nd[p*2+1].mx-nd[p*2+1].mn>c) return get(p*2+1,md+1,r,c);
	int ret=get(p*2,l,md,c);
	if (ret+nd[2*p+1].mn<=0) return nd[p*2+1].val-nd[p*2+1].mn;
	if (ret+nd[2*p+1].mx>c) return c-(nd[p*2+1].mx-nd[p*2+1].val);
	return ret+nd[p*2+1].val;
}
VI distribute_candies(VI c,VI l,VI r,VI v) {
	n=SZ(c),q=SZ(v);
	VI a(n);
	rep(i,0,q) {
		qs[l[i]].pb(mp(i,v[i]));
		qs[r[i]+1].pb(mp(i,-v[i]));
	}
	rep(i,0,n) {
		for (auto x:qs[i]) modify(1,0,q-1,x.fi,x.se);
		a[i]=get(1,0,q-1,c[i]);
	}
	return a;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28620 KB Output is correct
2 Correct 15 ms 28632 KB Output is correct
3 Correct 16 ms 28664 KB Output is correct
4 Correct 15 ms 28772 KB Output is correct
5 Correct 15 ms 28792 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 42712 KB Output is correct
2 Correct 352 ms 46788 KB Output is correct
3 Correct 304 ms 46624 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28620 KB Output is correct
2 Correct 173 ms 40824 KB Output is correct
3 Correct 75 ms 34484 KB Output is correct
4 Correct 319 ms 48580 KB Output is correct
5 Correct 364 ms 49100 KB Output is correct
6 Correct 348 ms 49404 KB Output is correct
7 Correct 325 ms 48856 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28620 KB Output is correct
2 Correct 14 ms 28620 KB Output is correct
3 Correct 90 ms 39156 KB Output is correct
4 Correct 63 ms 32344 KB Output is correct
5 Correct 155 ms 42548 KB Output is correct
6 Correct 143 ms 43228 KB Output is correct
7 Correct 164 ms 43704 KB Output is correct
8 Correct 150 ms 42348 KB Output is correct
9 Correct 155 ms 44016 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28620 KB Output is correct
2 Correct 15 ms 28632 KB Output is correct
3 Correct 16 ms 28664 KB Output is correct
4 Correct 15 ms 28772 KB Output is correct
5 Correct 15 ms 28792 KB Output is correct
6 Correct 306 ms 42712 KB Output is correct
7 Correct 352 ms 46788 KB Output is correct
8 Correct 304 ms 46624 KB Output is correct
9 Correct 15 ms 28620 KB Output is correct
10 Correct 173 ms 40824 KB Output is correct
11 Correct 75 ms 34484 KB Output is correct
12 Correct 319 ms 48580 KB Output is correct
13 Correct 364 ms 49100 KB Output is correct
14 Correct 348 ms 49404 KB Output is correct
15 Correct 325 ms 48856 KB Output is correct
16 Correct 13 ms 28620 KB Output is correct
17 Correct 14 ms 28620 KB Output is correct
18 Correct 90 ms 39156 KB Output is correct
19 Correct 63 ms 32344 KB Output is correct
20 Correct 155 ms 42548 KB Output is correct
21 Correct 143 ms 43228 KB Output is correct
22 Correct 164 ms 43704 KB Output is correct
23 Correct 150 ms 42348 KB Output is correct
24 Correct 155 ms 44016 KB Output is correct
25 Correct 14 ms 28632 KB Output is correct
26 Correct 66 ms 32344 KB Output is correct
27 Correct 176 ms 40448 KB Output is correct
28 Correct 329 ms 47300 KB Output is correct
29 Correct 334 ms 47580 KB Output is correct
30 Correct 305 ms 47964 KB Output is correct
31 Correct 334 ms 48040 KB Output is correct
32 Correct 322 ms 48232 KB Output is correct