oj.uz

Submission #889019

# Submission time Handle Problem Language Result Execution time Memory
889019 2023-12-18T15:30:27 Z BBart888 Wall (IOI14_wall) C++14
100 / 100
 776 ms 92048 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<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 0 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 212 ms 8584 KB Output is correct
3 Correct 173 ms 4692 KB Output is correct
4 Correct 486 ms 12332 KB Output is correct
5 Correct 268 ms 12844 KB Output is correct
6 Correct 250 ms 12624 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 7 ms 1112 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 6 ms 1116 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 210 ms 8308 KB Output is correct
9 Correct 168 ms 4404 KB Output is correct
10 Correct 473 ms 12176 KB Output is correct
11 Correct 256 ms 12624 KB Output is correct
12 Correct 257 ms 12796 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 213 ms 8432 KB Output is correct
15 Correct 32 ms 1712 KB Output is correct
16 Correct 632 ms 12580 KB Output is correct
17 Correct 261 ms 12540 KB Output is correct
18 Correct 266 ms 12444 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 7 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 0 ms 604 KB Output is correct
8 Correct 222 ms 8472 KB Output is correct
9 Correct 167 ms 4432 KB Output is correct
10 Correct 462 ms 12368 KB Output is correct
11 Correct 260 ms 12628 KB Output is correct
12 Correct 288 ms 12728 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 222 ms 8436 KB Output is correct
15 Correct 32 ms 1624 KB Output is correct
16 Correct 567 ms 12700 KB Output is correct
17 Correct 269 ms 12372 KB Output is correct
18 Correct 265 ms 12584 KB Output is correct
19 Correct 761 ms 92048 KB Output is correct
20 Correct 760 ms 89512 KB Output is correct
21 Correct 723 ms 91960 KB Output is correct
22 Correct 753 ms 89616 KB Output is correct
23 Correct 766 ms 89616 KB Output is correct
24 Correct 725 ms 89440 KB Output is correct
25 Correct 721 ms 89584 KB Output is correct
26 Correct 729 ms 91984 KB Output is correct
27 Correct 755 ms 91984 KB Output is correct
28 Correct 776 ms 89544 KB Output is correct
29 Correct 721 ms 89472 KB Output is correct
30 Correct 732 ms 89432 KB Output is correct