oj.uz

Submission #889015

# Submission time Handle Problem Language Result Execution time Memory
889015 2023-12-18T15:28:03 Z BBart888 Wall (IOI14_wall) C++14
100 / 100
 730 ms 123248 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN= 2e6+11;


int tmx[4*MAXN];
int tmn[4*MAXN];
pair<int,int> lazy[4*MAXN];

#define ff first
#define ss second


void pull_add(int x, int k){
    tmn[x] = max(tmn[x], k);
    tmx[x] = max(tmx[x], k);
    lazy[x].ff = max(lazy[x].ff, k);
    lazy[x].ss = max(lazy[x].ss, k);
}

void pull_dec(int x, int k){
    tmn[x] = min(tmn[x], k);
    tmx[x] = min(tmx[x], k);
    lazy[x].ff = min(lazy[x].ff, k);
    lazy[x].ss = min(lazy[x].ss, k);
}

void push(int x){
    if(lazy[x].ff != -1e9){
        pull_add(x << 1, lazy[x].ff);
        pull_add(x << 1 | 1, lazy[x].ff);
    }
    if(lazy[x].ss != 1e9){
        pull_dec(x << 1, lazy[x].ss);
        pull_dec(x << 1 | 1, lazy[x].ss);
    }
    lazy[x] = {-1e9, 1e9};
}



void upd(int v,int tl,int  tr,int l,int r,int type,int val)
{
	if(l > r)
		return;
	if(l == tl && tr ==r)
	{
			if(type == 1)
				pull_add(v,val);
			else
				pull_dec(v,val);
			return;
	}
	int tm =(tl+tr)/2;
	push(v);
	upd(2*v,tl,tm,l,min(r,tm),type,val);
	upd(2*v+1,tm+1,tr,max(l,tm+1),r,type,val);
	tmx[v] = max(tmx[2*v],tmx[2*v+1]);
	tmn[v] = min(tmn[2*v],tmn[2*v+1]);
}


int get(int v,int tl,int tr,int pos)
{
	if(tl == tr)
		return tmx[v];
	int tm =(tl+tr)/2;
	push(v);
	if(pos <= tm)
		return get(2*v,tl,tm,pos);
	else
		return get(2*v+1,tm+1,tr,pos);
}



void buildWall(int n,int k,int op[],int left[],
int right[],int height[],int finalHeight[])
{
	for(int i = 0;i<4*MAXN;i++)
		lazy[i] = {-1e9,1e9};
	
	for(int i =0;i<k;i++)
		{
			if(op[i] == 1)
				upd(1,0,MAXN,left[i],right[i],1,height[i]);
			else
				upd(1,0,MAXN,left[i],right[i],0,height[i]);
		}

	for(int i =0;i<n;i++)
		finalHeight[i] = get(1,0,MAXN,i);
		
	

}
/*

int main()
{
	cin.tie(0);
	cout.tie(0);
	
	
	
	
	upd(1,0,MAXN,1,5,1,6);
	upd(1,0,MAXN,4,5,0,3);
	
	
	
	for(int i =0;i<=10;i++)
		cout<<get(1,0,MAXN,i)<<" ";
			

	
	
	
	
	
	return 0;
}

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 74332 KB Output is correct
2 Correct 15 ms 74588 KB Output is correct
3 Correct 14 ms 70232 KB Output is correct
4 Correct 19 ms 74588 KB Output is correct
5 Correct 17 ms 74556 KB Output is correct
6 Correct 17 ms 70488 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 74328 KB Output is correct
2 Correct 219 ms 82256 KB Output is correct
3 Correct 187 ms 73948 KB Output is correct
4 Correct 485 ms 76168 KB Output is correct
5 Correct 274 ms 80380 KB Output is correct
6 Correct 264 ms 74596 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 74332 KB Output is correct
2 Correct 15 ms 74588 KB Output is correct
3 Correct 15 ms 70488 KB Output is correct
4 Correct 19 ms 74532 KB Output is correct
5 Correct 17 ms 74608 KB Output is correct
6 Correct 17 ms 70492 KB Output is correct
7 Correct 12 ms 74332 KB Output is correct
8 Correct 223 ms 82256 KB Output is correct
9 Correct 179 ms 73808 KB Output is correct
10 Correct 481 ms 76196 KB Output is correct
11 Correct 268 ms 80472 KB Output is correct
12 Correct 271 ms 74732 KB Output is correct
13 Correct 12 ms 74332 KB Output is correct
14 Correct 223 ms 82232 KB Output is correct
15 Correct 43 ms 71248 KB Output is correct
16 Correct 564 ms 80312 KB Output is correct
17 Correct 270 ms 83792 KB Output is correct
18 Correct 271 ms 80220 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 74412 KB Output is correct
2 Correct 15 ms 74532 KB Output is correct
3 Correct 13 ms 70236 KB Output is correct
4 Correct 19 ms 74548 KB Output is correct
5 Correct 17 ms 74584 KB Output is correct
6 Correct 17 ms 70488 KB Output is correct
7 Correct 13 ms 74332 KB Output is correct
8 Correct 226 ms 82172 KB Output is correct
9 Correct 180 ms 73952 KB Output is correct
10 Correct 485 ms 76168 KB Output is correct
11 Correct 270 ms 80424 KB Output is correct
12 Correct 270 ms 74576 KB Output is correct
13 Correct 12 ms 74332 KB Output is correct
14 Correct 224 ms 82172 KB Output is correct
15 Correct 43 ms 71248 KB Output is correct
16 Correct 559 ms 80468 KB Output is correct
17 Correct 271 ms 83796 KB Output is correct
18 Correct 279 ms 80280 KB Output is correct
19 Correct 724 ms 121680 KB Output is correct
20 Correct 719 ms 119244 KB Output is correct
21 Correct 730 ms 123232 KB Output is correct
22 Correct 725 ms 119360 KB Output is correct
23 Correct 727 ms 119320 KB Output is correct
24 Correct 727 ms 120656 KB Output is correct
25 Correct 728 ms 120696 KB Output is correct
26 Correct 720 ms 123248 KB Output is correct
27 Correct 724 ms 123216 KB Output is correct
28 Correct 726 ms 119380 KB Output is correct
29 Correct 720 ms 120720 KB Output is correct
30 Correct 729 ms 120752 KB Output is correct