oj.uz

Submission #889045

# Submission time Handle Problem Language Result Execution time Memory
889045 2023-12-18T17:03:31 Z BBart888 Wall (IOI14_wall) C++14
100 / 100
 694 ms 97608 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].ss != 1e9){
        pull_dec(x << 1, lazy[x].ss);
        pull_dec(x << 1 | 1, lazy[x].ss);
    }
	
    if(lazy[x].ff != -1e9){
        pull_add(x << 1, lazy[x].ff);
        pull_add(x << 1 | 1, lazy[x].ff);
    }
    
    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<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 1 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1372 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 179 ms 11736 KB Output is correct
3 Correct 140 ms 6736 KB Output is correct
4 Correct 385 ms 17592 KB Output is correct
5 Correct 224 ms 18028 KB Output is correct
6 Correct 212 ms 17448 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 3 ms 780 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 6 ms 1192 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1212 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 175 ms 11756 KB Output is correct
9 Correct 141 ms 6892 KB Output is correct
10 Correct 413 ms 17744 KB Output is correct
11 Correct 216 ms 18120 KB Output is correct
12 Correct 238 ms 17456 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 178 ms 11420 KB Output is correct
15 Correct 28 ms 2136 KB Output is correct
16 Correct 474 ms 17672 KB Output is correct
17 Correct 216 ms 17424 KB Output is correct
18 Correct 235 ms 17408 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 176 ms 11604 KB Output is correct
9 Correct 142 ms 6876 KB Output is correct
10 Correct 434 ms 17748 KB Output is correct
11 Correct 219 ms 18060 KB Output is correct
12 Correct 210 ms 17232 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 191 ms 11384 KB Output is correct
15 Correct 28 ms 2136 KB Output is correct
16 Correct 485 ms 17600 KB Output is correct
17 Correct 219 ms 17452 KB Output is correct
18 Correct 216 ms 17232 KB Output is correct
19 Correct 664 ms 97608 KB Output is correct
20 Correct 652 ms 94932 KB Output is correct
21 Correct 644 ms 97252 KB Output is correct
22 Correct 643 ms 94844 KB Output is correct
23 Correct 694 ms 94788 KB Output is correct
24 Correct 643 ms 94716 KB Output is correct
25 Correct 639 ms 94904 KB Output is correct
26 Correct 652 ms 97364 KB Output is correct
27 Correct 652 ms 97328 KB Output is correct
28 Correct 635 ms 94800 KB Output is correct
29 Correct 638 ms 94816 KB Output is correct
30 Correct 653 ms 95040 KB Output is correct