Submission #88421

# Submission time Handle Problem Language Result Execution time Memory
88421 2018-12-05T18:50:31 Z Pajaraja Wall (IOI14_wall) C++17
100 / 100
892 ms 164468 KB
#include "wall.h"
#include <bits/stdc++.h>
#define MAXN 2000007
using namespace std;
int seg[4*MAXN],poz[MAXN];
bool tr[4*MAXN];
void relax(int ind)
{
	if(seg[ind]==-1) return;
	seg[2*ind]=seg[2*ind+1]=seg[ind];
	seg[ind]=-1;
}
void upd(int l,int r,int lt, int rt,int val,bool b,int ind)
{
	if(r<lt || l>rt) return;
	if(l>=lt && r<=rt && seg[ind]!=-1)
	{
		if(b) seg[ind]=max(seg[ind],val);
		else seg[ind]=min(seg[ind],val);
		return;
	}
	relax(ind);
	int s=(l+r)/2;
	upd(l,s,lt,rt,val,b,2*ind); upd(s+1,r,lt,rt,val,b,2*ind+1);
	if(seg[2*ind]==seg[2*ind+1]) seg[ind]=seg[2*ind];
	else seg[ind]=-1; 
}
void loc(int l,int r,int ind)
{
	if(l==r) {poz[l]=ind; tr[ind]=true; return;}
	int s=(l+r)/2; loc(l,s,2*ind); loc(s+1,r,2*ind+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	loc(0,n-1,1);
	for(int i=0;i<k;i++) upd(0,n-1,left[i],right[i],height[i],op[i]==1,1);
	for(int i=1;i<poz[n-1];i++) if(!tr[i]) relax(i);
	for(int i=0;i<n;i++) finalHeight[i]=seg[poz[i]];
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 592 KB Output is correct
3 Correct 4 ms 648 KB Output is correct
4 Correct 10 ms 856 KB Output is correct
5 Correct 6 ms 988 KB Output is correct
6 Correct 7 ms 1004 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 1004 KB Output is correct
2 Correct 174 ms 8420 KB Output is correct
3 Correct 249 ms 8420 KB Output is correct
4 Correct 710 ms 10592 KB Output is correct
5 Correct 336 ms 11252 KB Output is correct
6 Correct 316 ms 11252 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 11252 KB Output is correct
2 Correct 4 ms 11252 KB Output is correct
3 Correct 4 ms 11252 KB Output is correct
4 Correct 10 ms 11252 KB Output is correct
5 Correct 8 ms 11252 KB Output is correct
6 Correct 7 ms 11252 KB Output is correct
7 Correct 2 ms 11252 KB Output is correct
8 Correct 173 ms 11252 KB Output is correct
9 Correct 248 ms 11252 KB Output is correct
10 Correct 703 ms 11252 KB Output is correct
11 Correct 330 ms 11252 KB Output is correct
12 Correct 308 ms 11252 KB Output is correct
13 Correct 2 ms 11252 KB Output is correct
14 Correct 173 ms 11252 KB Output is correct
15 Correct 49 ms 11252 KB Output is correct
16 Correct 892 ms 11252 KB Output is correct
17 Correct 330 ms 11252 KB Output is correct
18 Correct 322 ms 11252 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 11252 KB Output is correct
2 Correct 3 ms 11252 KB Output is correct
3 Correct 4 ms 11252 KB Output is correct
4 Correct 10 ms 11252 KB Output is correct
5 Correct 7 ms 11252 KB Output is correct
6 Correct 7 ms 11252 KB Output is correct
7 Correct 2 ms 11252 KB Output is correct
8 Correct 169 ms 11252 KB Output is correct
9 Correct 248 ms 11252 KB Output is correct
10 Correct 705 ms 11252 KB Output is correct
11 Correct 336 ms 11324 KB Output is correct
12 Correct 317 ms 11324 KB Output is correct
13 Correct 2 ms 11324 KB Output is correct
14 Correct 174 ms 11324 KB Output is correct
15 Correct 49 ms 11324 KB Output is correct
16 Correct 890 ms 11324 KB Output is correct
17 Correct 328 ms 11324 KB Output is correct
18 Correct 334 ms 11324 KB Output is correct
19 Correct 715 ms 53640 KB Output is correct
20 Correct 713 ms 61772 KB Output is correct
21 Correct 718 ms 74664 KB Output is correct
22 Correct 696 ms 82692 KB Output is correct
23 Correct 690 ms 93280 KB Output is correct
24 Correct 682 ms 103656 KB Output is correct
25 Correct 691 ms 113936 KB Output is correct
26 Correct 707 ms 126412 KB Output is correct
27 Correct 719 ms 136252 KB Output is correct
28 Correct 706 ms 144280 KB Output is correct
29 Correct 714 ms 153828 KB Output is correct
30 Correct 726 ms 164468 KB Output is correct