oj.uz

Submission #435902

# Submission time Handle Problem Language Result Execution time Memory
435902 2021-06-23T22:56:34 Z rqi Distributing Candies (IOI21_candies) C++17
100 / 100
 3918 ms 33984 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define ins insert
#define bk back()
#define lb lower_bound

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

void ckmin(ll& a, ll b){
	a = min(a, b);
}

void ckmax(ll& a, ll b){
	a = max(a, b);
}

const ll INF = 1e18;
const int MOD = 1e9+7;

const int mx = 200005;
const int SZ = 262144;

pl mnmx[2*SZ];
ll lazy[2*SZ];

void pull(int ind){
	mnmx[ind] = mp(min(mnmx[2*ind].f, mnmx[2*ind+1].f), max(mnmx[2*ind].s, mnmx[2*ind+1].s));
}

void build(){
	for(int i = SZ-1; i >= 1; i--){
		pull(i);
	}
}

void push(int ind){
	mnmx[ind].f+=lazy[ind];
	mnmx[ind].s+=lazy[ind];
		
	if(2*ind+1 < 2*SZ){
		for(int i = 0; i < 2; i++){
			assert(2*ind+i < 2*SZ);
			lazy[2*ind+i]+=lazy[ind];
		}
	}
	

	lazy[ind] = 0;
}



void update(int l, int r, ll val, int ind = 1, int L = 0, int R = SZ-1){
	push(ind);
	if(l > R || r < L) return;
	if(l <= L && R <= r){
		lazy[ind]+=val;
		push(ind);
		return;
	}

	int M = (L+R)/2;

	update(l, r, val, 2*ind, L, M);
	update(l, r, val, 2*ind+1, M+1, R);

	pull(ind);
}

ll tot_sum = 0;

// int query(ll D, pl q_MNMX = mp(INF, -INF), int ind = 1, int L = 0, int R = SZ-1){ //return -1 if inconclusive
// 	push(ind);

// 	// if(D == 17 && R <= 9){
// 	// 	cout << "L, R: " << L << " " << R << " " << q_MNMX.f << " " << q_MNMX.s << "\n";
// 	// 	cout << mnmx[ind].f << " " << mnmx[ind].s << "\n";
// 	// }

// 	pl entire = mp(min(q_MNMX.f, mnmx[ind].f), max(q_MNMX.s, mnmx[ind].s));

// 	if(q_MNMX.s-q_MNMX.f >= D) return MOD;

// 	// if(L == 2 && R == 3){
// 	// 	cout << "entire: " << entire.f << " " << entire.s << "\n";
// 	// }
// 	if(entire.s-entire.f < D) return L;

// 	// if(L == 2 && R == 3){
// 	// 	cout << "entire: " << entire.f << " " << entire.s << "\n";
// 	// }
// 	if(L == R){
// 		return MOD;
// 	}

// 	int M = (L+R)/2;

	
// 	// cout << L << " " << R << " " << "querying second half" << "\n";
// 	int res = query(D, q_MNMX, 2*ind+1, M+1, R);
// 	if(res > M+1){
// 		return res;
// 	}

// 	assert(res == M+1);

// 	pl half = mp(min(q_MNMX.f, mnmx[2*ind+1].f), max(q_MNMX.s, mnmx[2*ind+1].s));
// 	int res2 = query(D, half, 2*ind, L, M);

// 	res = min(res, res2);

// 	// if(D == 17 && R <= 9){
// 	// 	cout << "L, R:" << L << " " << R << "\n";
// 	// 	cout << "res: " << res << "\n";
// 	// }
// 	return res;
// }

pl queryMnMx(int l, int r, int ind = 1, int L = 0, int R = SZ-1){
	push(ind);

	if(r < L || R < l) return mp(INF, -INF);

	if(l <= L && R <= r){
		return mnmx[ind];
	}

	int M = (L+R)/2;
	pl res1 = queryMnMx(l, r, 2*ind, L, M);
	pl res2 = queryMnMx(l, r, 2*ind+1, M+1, R);

	return mp(min(res1.f, res2.f), max(res1.s, res2.s));
}

int n, q;

int query(ll D){
	int lo = 0;
	int hi = q;
	while(lo < hi){
		int mid = (lo+hi)/2;

		bool works = 0;

		pl a = queryMnMx(mid, q);
		if(a.s-a.f < D){
			works = 1;
		}

		if(works){
			hi = mid;
		}
		else{
			lo = mid+1;
		}
	}
	return lo;
}

vector<pair<int, ll>> updates[mx];

vi distribute_candies(vi c, vi l, vi r, vi v) {
    n = sz(c);
    q = sz(l);
    vi s(n, 0);

    for(int i = 0; i < q; i++){
    	updates[l[i]].pb(mp(i, v[i]));
    	updates[r[i]+1].pb(mp(i, -v[i]));
    }

    for(int i = q+1; i < SZ; i++){
    	mnmx[SZ+i] = mp(INF, -INF);
    }
    build();

    for(int i = 0; i < n; i++){
    	// cout << "i = " << i << "\n";
    	for(auto u: updates[i]){
    		update(u.f+1, q, u.s);
    	}

    	ll D = c[i];
    	ll tot = queryMnMx(q, q).f;

    	int pos = query(D);

    	// cout << D << " " << tot << " " << pos << "\n";
    	// cout.flush();


   		if(pos == 0){
   			pl a = queryMnMx(0, q);
   			s[i] = (int)(tot-a.f);
   		}
   		else{
   			// cout << "seg: ";
   			// for(int i = 0; i <= q; i++){
   			// 	pl a = queryMnMx(i, i);
   			// 	cout << a.f << " ";
   			// }
   			// cout << "\n";
   			// cout.flush();
   			pl a = queryMnMx(pos-1, q);
   			ll ext_val = queryMnMx(pos-1, pos-1).f;


   			// cout << a.f << " " << a.s << " " << ext_val << "\n";
   			// cout.flush();
   			if(ext_val == a.f){
   				s[i] = (int)(D-(a.s-tot));
   			}
   			else{
   				assert(ext_val == a.s);
   				s[i] = (int)(tot-a.f);
   			}
   		}
    }

    return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13132 KB Output is correct
2 Correct 9 ms 13132 KB Output is correct
3 Correct 12 ms 13388 KB Output is correct
4 Correct 13 ms 13456 KB Output is correct
5 Correct 27 ms 13388 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3226 ms 33860 KB Output is correct
2 Correct 3375 ms 33964 KB Output is correct
3 Correct 3505 ms 33860 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13260 KB Output is correct
2 Correct 570 ms 29948 KB Output is correct
3 Correct 1752 ms 16868 KB Output is correct
4 Correct 3918 ms 33880 KB Output is correct
5 Correct 3683 ms 33876 KB Output is correct
6 Correct 3134 ms 33928 KB Output is correct
7 Correct 3031 ms 33876 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13132 KB Output is correct
2 Correct 11 ms 13268 KB Output is correct
3 Correct 277 ms 27412 KB Output is correct
4 Correct 1552 ms 15872 KB Output is correct
5 Correct 2829 ms 29956 KB Output is correct
6 Correct 2710 ms 29912 KB Output is correct
7 Correct 2500 ms 29912 KB Output is correct
8 Correct 2834 ms 29976 KB Output is correct
9 Correct 3322 ms 29904 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13132 KB Output is correct
2 Correct 9 ms 13132 KB Output is correct
3 Correct 12 ms 13388 KB Output is correct
4 Correct 13 ms 13456 KB Output is correct
5 Correct 27 ms 13388 KB Output is correct
6 Correct 3226 ms 33860 KB Output is correct
7 Correct 3375 ms 33964 KB Output is correct
8 Correct 3505 ms 33860 KB Output is correct
9 Correct 12 ms 13260 KB Output is correct
10 Correct 570 ms 29948 KB Output is correct
11 Correct 1752 ms 16868 KB Output is correct
12 Correct 3918 ms 33880 KB Output is correct
13 Correct 3683 ms 33876 KB Output is correct
14 Correct 3134 ms 33928 KB Output is correct
15 Correct 3031 ms 33876 KB Output is correct
16 Correct 9 ms 13132 KB Output is correct
17 Correct 11 ms 13268 KB Output is correct
18 Correct 277 ms 27412 KB Output is correct
19 Correct 1552 ms 15872 KB Output is correct
20 Correct 2829 ms 29956 KB Output is correct
21 Correct 2710 ms 29912 KB Output is correct
22 Correct 2500 ms 29912 KB Output is correct
23 Correct 2834 ms 29976 KB Output is correct
24 Correct 3322 ms 29904 KB Output is correct
25 Correct 10 ms 13152 KB Output is correct
26 Correct 1501 ms 15800 KB Output is correct
27 Correct 561 ms 29940 KB Output is correct
28 Correct 3420 ms 33984 KB Output is correct
29 Correct 3273 ms 33856 KB Output is correct
30 Correct 3251 ms 33852 KB Output is correct
31 Correct 3091 ms 33936 KB Output is correct
32 Correct 3035 ms 33860 KB Output is correct