oj.uz

Submission #593552

# Submission time Handle Problem Language Result Execution time Memory
593552 2022-07-11T11:31:42 Z LastRonin Distributing Candies (IOI21_candies) C++17
100 / 100
 1057 ms 32252 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
#define pill pair<ll, ll>
#define mp make_pair
#define f first
#define s second
#define pb push_back

using namespace std;

const ll N = 3e5;

ll n, m;

struct seg {
	ll mx[4 * N] = {0};
	ll mn[4 * N] = {0};
	ll p[4 * N] = {0};
	void push(ll v, ll tl, ll tr) {
		mx[v] += p[v];
		mn[v] += p[v];
		if(tl != tr) {
			p[v * 2] += p[v];
			p[v * 2 + 1] += p[v];
		}
		p[v] = 0;
	}
	void build(ll v = 1, ll tl = 0, ll tr = m + 1) {
		mx[v] = mn[v] = 0;
		p[v] = 0;
		if(tl == tr) { 
			return;
		}
		ll m = (tl + tr) >> 1ll;
		build(v * 2, tl, m);
		build(v * 2 + 1, m + 1, tr);
	}
	void upd(ll l, ll r, ll z, ll v = 1, ll tl = 0, ll tr = m + 1) {
		push(v, tl, tr);
		if(l > tr || tl > r)return;
		if(l <= tl && tr <= r) {
			p[v] += z;
			push(v, tl, tr);
			return;
		}
		ll m = (tl + tr) >> 1ll;
		upd(l, r, z, v * 2, tl, m);
		upd(l, r, z, v * 2 + 1, m + 1, tr);
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
	}
	pill get(ll l, ll r, ll v = 1, ll tl = 0, ll tr = m + 1) {
		push(v, tl, tr);
		if(l > tr || tl > r)return mp(1e17, -1e17);
		if(l <= tl && tr <= r)return mp(mn[v], mx[v]);
		ll m = (tl + tr) >> 1ll;
		pill a = get(l, r, v * 2, tl, m);
		pill b = get(l, r, v * 2 + 1, m + 1, tr);
		return mp(min(a.f, b.f), max(a.s, b.s));
	}
} rt;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = c.size();
    m = l.size();
  	rt.build();  
    vector<int> s(n);
	vector<int> scan[n + 2];
	for(int i = 0; i < l.size(); i++) {
		scan[l[i]].pb(i);
		scan[r[i] + 1].pb(i);
	}

	for(int i = 0; i < n; i++) {
		for(auto u : scan[i]) {
			if(r[u] + 1 == i) {
				rt.upd(u + 1, m + 1, -v[u]);					
			} else {
				rt.upd(u + 1, m + 1, v[u]);
			}
		}
		ll L = 0, R = m + 1, ans = -1;
		while(L <= R) {
			ll M = (L + R) >> 1ll;
			pill z = rt.get(M, m + 1);
			if(z.s - z.f >= c[i]) {
				ans = M;
				L = M + 1;				
			} else {
				R = M - 1;
			}
		}
		ll zn = rt.get(m + 1, m + 1).f;
		if(ans == -1) {
			pill z2 = rt.get(ans + 1, m + 1);
			s[i] = zn - z2.f;			
			continue;	
		} else {
			pill z = rt.get(ans + 1, m + 1);
			pill z2 = rt.get(ans, m + 1);
			if(z2.s == z.s) {
				s[i] = c[i] - (z.s - zn);		
			} else {
				s[i] = (zn - z.f);
			}
		}
	//	if(s[i] < 0 || s[i] > c[i])assert(0);
	}
    return s;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < l.size(); i++) {
      |                 ~~^~~~~~~~~~

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 468 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 5 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 30508 KB Output is correct
2 Correct 1032 ms 30484 KB Output is correct
3 Correct 1043 ms 30480 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 252 ms 22096 KB Output is correct
3 Correct 315 ms 10940 KB Output is correct
4 Correct 1049 ms 32236 KB Output is correct
5 Correct 961 ms 32252 KB Output is correct
6 Correct 1000 ms 32156 KB Output is correct
7 Correct 996 ms 32132 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 117 ms 19548 KB Output is correct
4 Correct 248 ms 8740 KB Output is correct
5 Correct 752 ms 28608 KB Output is correct
6 Correct 775 ms 28608 KB Output is correct
7 Correct 786 ms 28608 KB Output is correct
8 Correct 856 ms 28356 KB Output is correct
9 Correct 792 ms 28348 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 468 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 1057 ms 30508 KB Output is correct
7 Correct 1032 ms 30484 KB Output is correct
8 Correct 1043 ms 30480 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 252 ms 22096 KB Output is correct
11 Correct 315 ms 10940 KB Output is correct
12 Correct 1049 ms 32236 KB Output is correct
13 Correct 961 ms 32252 KB Output is correct
14 Correct 1000 ms 32156 KB Output is correct
15 Correct 996 ms 32132 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 117 ms 19548 KB Output is correct
19 Correct 248 ms 8740 KB Output is correct
20 Correct 752 ms 28608 KB Output is correct
21 Correct 775 ms 28608 KB Output is correct
22 Correct 786 ms 28608 KB Output is correct
23 Correct 856 ms 28356 KB Output is correct
24 Correct 792 ms 28348 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 235 ms 8836 KB Output is correct
27 Correct 279 ms 21900 KB Output is correct
28 Correct 963 ms 32152 KB Output is correct
29 Correct 1014 ms 32148 KB Output is correct
30 Correct 994 ms 32188 KB Output is correct
31 Correct 1034 ms 32144 KB Output is correct
32 Correct 1037 ms 32144 KB Output is correct