oj.uz

Submission #917251

# Submission time Handle Problem Language Result Execution time Memory
917251 2024-01-27T14:11:12 Z jamjanek Distributing Candies (IOI21_candies) C++17
100 / 100
 717 ms 33720 KB 
#include<bits/stdc++.h>
using namespace std;

long long c[200010];

struct node{long long mini, maxi, lazy;};
const int base = 1<<18;
node tree[2*base];

void push(int w){
	if(w>=base)return;
	tree[w*2].lazy+=tree[w].lazy;
	tree[w*2+1].lazy+=tree[w].lazy;
	tree[w*2].mini+=tree[w].lazy;
	tree[w*2].maxi+=tree[w].lazy;
	tree[w*2+1].mini+=tree[w].lazy;
	tree[w*2+1].maxi+=tree[w].lazy;
	tree[w].lazy = 0;
}

void update(int w, int l, int p, int a, int b, long long val){
	push(w);
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		tree[w].lazy+=val;
		tree[w].maxi+=val;
		tree[w].mini+=val;
		return;
	}
	update(w*2, l, (l+p)/2, a, b, val);
	update(w*2+1, (l+p)/2+1, p, a, b, val);
	tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
	tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}

long long maxi(int w, int l, int p, int a, int b){
	push(w);
	if(l>b || p<a)return -1000000000000000000;
	if(a<=l && p<=b){
		return tree[w].maxi;
	}
	return max(maxi(w*2, l, (l+p)/2, a, b), maxi(w*2+1, (l+p)/2+1, p, a, b));
//	tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
//	tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}


long long mini(int w, int l, int p, int a, int b){
	push(w);
	if(l>b || p<a)return 1000000000000000000;
	if(a<=l && p<=b){
		return tree[w].mini;
	}
	return min(mini(w*2, l, (l+p)/2, a, b), mini(w*2+1, (l+p)/2+1, p, a, b));
//	tree[w].mini = min(tree[w*2].mini, tree[w*2+1].mini);
//	tree[w].maxi = max(tree[w*2].maxi, tree[w*2+1].maxi);
}


vector<int> distribute_candies(vector<int>C, vector<int>l, vector<int>r, vector<int> V)
{
    vector<int>ans;
	int n, q, i, a, b, v;
	n = C.size();
	for(i=0;i<n;i++)
		c[i] = C[i];
	q = l.size();
	vector<pair<int,pair<int,int>>>sorted;
	for(i=1;i<=q;i++){
	    a = l[i-1];
	    b = r[i-1];
	    v = V[i-1];
		scanf("%d%d%d", &a, &b, &v);
		sorted.push_back({a, {i, v}});
		sorted.push_back({b+1, {i, -v}});
	}
	for(i=q+1;i<base;i++){
		tree[base+i].mini = 1000000000000000000;
		tree[base+i].maxi = -1000000000000000000;
	}
	for(i=base-1;i>0;i--){
		tree[i].maxi = max(tree[i*2].maxi, tree[i*2+1].maxi);
		tree[i].mini = min(tree[i*2].mini, tree[i*2+1].mini);
	}
	sort(sorted.begin(), sorted.end());
	int it = 0;
	for(i=0;i<n;i++){
		while(it<(int)sorted.size() && sorted[it].first==i){
			update(1, 0, base-1, sorted[it].second.first, q, sorted[it].second.second);
			it++;
		}
		int p;
		if(tree[1].maxi-tree[1].mini>=c[i]){
			int w = 1;
			long long sufMAX = -1000000000000000000, sufMIN = 1000000000000000000;
			while(w<base){
				push(w);
				if(max(sufMAX, tree[w*2+1].maxi)-min(sufMIN, tree[w*2+1].mini)>=c[i])
					w = w*2+1;
				else{
					sufMAX = max(sufMAX, tree[w*2+1].maxi);
					sufMIN = min(sufMIN, tree[w*2+1].mini);
					w = w*2;
				}
			}
			p = w-base;
		}
		else{
			p = -1;
		}

		if(p==-1)
			ans.push_back(mini(1, 0, base-1, q, q)-mini(1, 0, base-1, 0, q));
		else{
			if(mini(1, 0, base-1, p, q)==mini(1, 0, base-1, p, p))
				ans.push_back(mini(1, 0, base-1, q, q)-maxi(1, 0, base-1, p, q)+c[i]);
			else
				ans.push_back(mini(1, 0, base-1, q, q)-mini(1, 0, base-1, p, q));
		}
	}
	return ans;
}

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:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d%d%d", &a, &b, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 5 ms 12892 KB Output is correct
4 Correct 5 ms 12992 KB Output is correct
5 Correct 9 ms 13000 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 27724 KB Output is correct
2 Correct 636 ms 31200 KB Output is correct
3 Correct 711 ms 32124 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 367 ms 25232 KB Output is correct
3 Correct 271 ms 20164 KB Output is correct
4 Correct 681 ms 32884 KB Output is correct
5 Correct 717 ms 33592 KB Output is correct
6 Correct 627 ms 33720 KB Output is correct
7 Correct 611 ms 33232 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 5 ms 13344 KB Output is correct
3 Correct 180 ms 25028 KB Output is correct
4 Correct 230 ms 18144 KB Output is correct
5 Correct 410 ms 30396 KB Output is correct
6 Correct 435 ms 32608 KB Output is correct
7 Correct 453 ms 32992 KB Output is correct
8 Correct 404 ms 30652 KB Output is correct
9 Correct 502 ms 32140 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 5 ms 12892 KB Output is correct
4 Correct 5 ms 12992 KB Output is correct
5 Correct 9 ms 13000 KB Output is correct
6 Correct 669 ms 27724 KB Output is correct
7 Correct 636 ms 31200 KB Output is correct
8 Correct 711 ms 32124 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 367 ms 25232 KB Output is correct
11 Correct 271 ms 20164 KB Output is correct
12 Correct 681 ms 32884 KB Output is correct
13 Correct 717 ms 33592 KB Output is correct
14 Correct 627 ms 33720 KB Output is correct
15 Correct 611 ms 33232 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 5 ms 13344 KB Output is correct
18 Correct 180 ms 25028 KB Output is correct
19 Correct 230 ms 18144 KB Output is correct
20 Correct 410 ms 30396 KB Output is correct
21 Correct 435 ms 32608 KB Output is correct
22 Correct 453 ms 32992 KB Output is correct
23 Correct 404 ms 30652 KB Output is correct
24 Correct 502 ms 32140 KB Output is correct
25 Correct 3 ms 12892 KB Output is correct
26 Correct 186 ms 18156 KB Output is correct
27 Correct 327 ms 25540 KB Output is correct
28 Correct 560 ms 31632 KB Output is correct
29 Correct 596 ms 32848 KB Output is correct
30 Correct 697 ms 33208 KB Output is correct
31 Correct 619 ms 33572 KB Output is correct
32 Correct 637 ms 33144 KB Output is correct