oj.uz

Submission #604191

# Submission time Handle Problem Language Result Execution time Memory
604191 2022-07-24T20:31:35 Z sofapuden Distributing Candies (IOI21_candies) C++17
100 / 100
 1649 ms 48008 KB 
#include "candies.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct ST { 
	struct R {
		ll mn, mx;
		R() : mn(1ll<<60), mx(-(1ll<<60)) {}
		R(int x) : mn(x), mx(x) {}
	};

	int n;
	vector<R> st;
	vector<ll> lazy;

	ST(int sz) : n(sz), st(4*n,0), lazy(4*n,0) {}

	R mer(R a, R b){
		R c;
		c.mn = min(a.mn,b.mn);
		c.mx = max(a.mx,b.mx);
		return c;
	}

	void push(int p){
		st[p].mn+=lazy[p];
		st[p].mx+=lazy[p];
		if((p<<1|1) < 4*n){
			lazy[p<<1]+=lazy[p];
			lazy[p<<1|1]+=lazy[p];
		}
		lazy[p] = 0;
	}

	void update(int i, int j, ll v, int l, int r, int p){
		push(p);
		if(l >= i && r <= j){
			lazy[p]+=v;
			push(p);
			return;
		}
		if(l > j || r < i)return;
		int m = (l+r)>>1;
		update(i,j,v,l,m,p<<1);
		update(i,j,v,m+1,r,p<<1|1);
		st[p] = mer(st[p<<1],st[p<<1|1]);
	}

	R que(int i, int j, int l, int r, int p){
		push(p);
		if(l >= i && r <= j)return st[p];
		if(l > j || r < i)return R();
		int m = (l+r)>>1;
		return mer(que(i,j,l,m,p<<1), que(i,j,m+1,r,p<<1|1));
	}
};

struct T {
	ll x, i;
	T(int _x, int _i) : x(_x), i(_i) {}
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    int q = l.size();
    vector<vector<T>> am(n+1);
    for(int i = 0; i < q; ++i){
	    am[l[i]].emplace_back(v[i],i+1);
	    am[r[i]+1].emplace_back(-v[i],i+1);
    }
    ST S(q+1);

    vector<int> ans(n,0);

    for(int i = 0; i < n; ++i){
	    for(auto x : am[i]){
		    S.update(x.i,q,x.x,0,q,1);
	    }
	    ll a = -(1ll<<60), b = (1ll<<60);
	    int l = 0, r = q;
	    while(l <= r){
		    int m = (l+r) >> 1;
		    auto x = S.que(m,q,0,q,1);
		    if(x.mx-x.mn >= c[i]){
			    a = max(a,x.mn);
			    b = min(b,x.mx);
			    l = m+1;
		    }
		    else {
			    r = m-1;
		    }
	    }
	    auto x = S.que(l,q,0,q,1);
	    if(l == 0){
		    a = x.mn, b = c[i]-x.mn;
	    }
	    if(x.mn == a)ans[i] = (int)(S.que(q,q,0,q,1).mn-a);
	    else ans[i] = (int)(c[i] - (b - S.que(q,q,0,q,1).mn));
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 6 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1649 ms 41292 KB Output is correct
2 Correct 1516 ms 41304 KB Output is correct
3 Correct 1484 ms 41300 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 256 ms 35700 KB Output is correct
3 Correct 390 ms 9768 KB Output is correct
4 Correct 1455 ms 47224 KB Output is correct
5 Correct 1386 ms 47692 KB Output is correct
6 Correct 1479 ms 48008 KB Output is correct
7 Correct 1536 ms 47344 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 153 ms 30352 KB Output is correct
4 Correct 371 ms 8752 KB Output is correct
5 Correct 1247 ms 40636 KB Output is correct
6 Correct 1259 ms 41308 KB Output is correct
7 Correct 1278 ms 41916 KB Output is correct
8 Correct 1196 ms 40532 KB Output is correct
9 Correct 1274 ms 42012 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 1649 ms 41292 KB Output is correct
7 Correct 1516 ms 41304 KB Output is correct
8 Correct 1484 ms 41300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 256 ms 35700 KB Output is correct
11 Correct 390 ms 9768 KB Output is correct
12 Correct 1455 ms 47224 KB Output is correct
13 Correct 1386 ms 47692 KB Output is correct
14 Correct 1479 ms 48008 KB Output is correct
15 Correct 1536 ms 47344 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 153 ms 30352 KB Output is correct
19 Correct 371 ms 8752 KB Output is correct
20 Correct 1247 ms 40636 KB Output is correct
21 Correct 1259 ms 41308 KB Output is correct
22 Correct 1278 ms 41916 KB Output is correct
23 Correct 1196 ms 40532 KB Output is correct
24 Correct 1274 ms 42012 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 342 ms 8908 KB Output is correct
27 Correct 283 ms 35280 KB Output is correct
28 Correct 1416 ms 45876 KB Output is correct
29 Correct 1473 ms 46232 KB Output is correct
30 Correct 1507 ms 46424 KB Output is correct
31 Correct 1533 ms 46616 KB Output is correct
32 Correct 1538 ms 46816 KB Output is correct