oj.uz

Submission #917252

# Submission time Handle Problem Language Result Execution time Memory
917252 2024-01-27T14:11:56 Z jamjanek Distributing Candies (IOI21_candies) C++17
100 / 100
 3376 ms 28420 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 = -1, k = q, s;
		while(p<k){
			s = (p+k+1)/2;
			if(maxi(1, 0, base-1, s, q)-mini(1, 0, base-1, s, q)<c[i])
				k = s-1;
			else
				p = s;
		}

		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 3 ms 12892 KB Output is correct
3 Correct 6 ms 12888 KB Output is correct
4 Correct 6 ms 12888 KB Output is correct
5 Correct 19 ms 13084 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2874 ms 26924 KB Output is correct
2 Correct 3052 ms 27228 KB Output is correct
3 Correct 3103 ms 27832 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 379 ms 22684 KB Output is correct
3 Correct 1548 ms 17924 KB Output is correct
4 Correct 3376 ms 27300 KB Output is correct
5 Correct 3324 ms 28264 KB Output is correct
6 Correct 2814 ms 26952 KB Output is correct
7 Correct 2836 ms 28148 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 6 ms 12888 KB Output is correct
3 Correct 200 ms 23644 KB Output is correct
4 Correct 1399 ms 17152 KB Output is correct
5 Correct 2895 ms 27720 KB Output is correct
6 Correct 2676 ms 28420 KB Output is correct
7 Correct 2577 ms 27688 KB Output is correct
8 Correct 2808 ms 28392 KB Output is correct
9 Correct 3231 ms 27524 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 3 ms 12892 KB Output is correct
3 Correct 6 ms 12888 KB Output is correct
4 Correct 6 ms 12888 KB Output is correct
5 Correct 19 ms 13084 KB Output is correct
6 Correct 2874 ms 26924 KB Output is correct
7 Correct 3052 ms 27228 KB Output is correct
8 Correct 3103 ms 27832 KB Output is correct
9 Correct 5 ms 12888 KB Output is correct
10 Correct 379 ms 22684 KB Output is correct
11 Correct 1548 ms 17924 KB Output is correct
12 Correct 3376 ms 27300 KB Output is correct
13 Correct 3324 ms 28264 KB Output is correct
14 Correct 2814 ms 26952 KB Output is correct
15 Correct 2836 ms 28148 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 6 ms 12888 KB Output is correct
18 Correct 200 ms 23644 KB Output is correct
19 Correct 1399 ms 17152 KB Output is correct
20 Correct 2895 ms 27720 KB Output is correct
21 Correct 2676 ms 28420 KB Output is correct
22 Correct 2577 ms 27688 KB Output is correct
23 Correct 2808 ms 28392 KB Output is correct
24 Correct 3231 ms 27524 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 1352 ms 17400 KB Output is correct
27 Correct 367 ms 22608 KB Output is correct
28 Correct 2993 ms 28336 KB Output is correct
29 Correct 2980 ms 27948 KB Output is correct
30 Correct 2966 ms 27936 KB Output is correct
31 Correct 2875 ms 27580 KB Output is correct
32 Correct 2771 ms 27188 KB Output is correct