oj.uz

Submission #917254

# Submission time Handle Problem Language Result Execution time Memory
917254 2024-01-27T14:13:27 Z jamjanek Distributing Candies (IOI21_candies) C++17
100 / 100
 695 ms 28436 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:12: 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 6 ms 12892 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 8 ms 12892 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 27324 KB Output is correct
2 Correct 643 ms 27320 KB Output is correct
3 Correct 613 ms 27320 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12892 KB Output is correct
2 Correct 359 ms 23128 KB Output is correct
3 Correct 275 ms 17884 KB Output is correct
4 Correct 664 ms 27056 KB Output is correct
5 Correct 695 ms 27092 KB Output is correct
6 Correct 628 ms 27664 KB Output is correct
7 Correct 658 ms 27708 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 4 ms 12888 KB Output is correct
3 Correct 176 ms 22364 KB Output is correct
4 Correct 221 ms 17064 KB Output is correct
5 Correct 417 ms 26920 KB Output is correct
6 Correct 422 ms 27832 KB Output is correct
7 Correct 445 ms 28136 KB Output is correct
8 Correct 396 ms 27932 KB Output is correct
9 Correct 495 ms 28084 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 6 ms 12892 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 8 ms 12892 KB Output is correct
6 Correct 641 ms 27324 KB Output is correct
7 Correct 643 ms 27320 KB Output is correct
8 Correct 613 ms 27320 KB Output is correct
9 Correct 5 ms 12892 KB Output is correct
10 Correct 359 ms 23128 KB Output is correct
11 Correct 275 ms 17884 KB Output is correct
12 Correct 664 ms 27056 KB Output is correct
13 Correct 695 ms 27092 KB Output is correct
14 Correct 628 ms 27664 KB Output is correct
15 Correct 658 ms 27708 KB Output is correct
16 Correct 3 ms 12888 KB Output is correct
17 Correct 4 ms 12888 KB Output is correct
18 Correct 176 ms 22364 KB Output is correct
19 Correct 221 ms 17064 KB Output is correct
20 Correct 417 ms 26920 KB Output is correct
21 Correct 422 ms 27832 KB Output is correct
22 Correct 445 ms 28136 KB Output is correct
23 Correct 396 ms 27932 KB Output is correct
24 Correct 495 ms 28084 KB Output is correct
25 Correct 3 ms 12892 KB Output is correct
26 Correct 189 ms 17136 KB Output is correct
27 Correct 348 ms 22468 KB Output is correct
28 Correct 567 ms 28436 KB Output is correct
29 Correct 613 ms 27064 KB Output is correct
30 Correct 618 ms 27092 KB Output is correct
31 Correct 660 ms 26956 KB Output is correct
32 Correct 636 ms 27132 KB Output is correct