Submission #88420

# Submission time Handle Problem Language Result Execution time Memory
88420 2018-12-05T18:48:06 Z Pajaraja Wall (IOI14_wall) C++17
61 / 100
911 ms 40800 KB
#include "wall.h"
#include <bits/stdc++.h>
#define MAXN 1000007
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 504 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 10 ms 1108 KB Output is correct
5 Correct 7 ms 1260 KB Output is correct
6 Correct 7 ms 1260 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 1260 KB Output is correct
2 Correct 169 ms 11260 KB Output is correct
3 Correct 246 ms 11260 KB Output is correct
4 Correct 693 ms 13488 KB Output is correct
5 Correct 331 ms 14000 KB Output is correct
6 Correct 313 ms 14124 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 14124 KB Output is correct
2 Correct 4 ms 14124 KB Output is correct
3 Correct 4 ms 14124 KB Output is correct
4 Correct 10 ms 14124 KB Output is correct
5 Correct 7 ms 14124 KB Output is correct
6 Correct 7 ms 14124 KB Output is correct
7 Correct 2 ms 14124 KB Output is correct
8 Correct 173 ms 14124 KB Output is correct
9 Correct 255 ms 14124 KB Output is correct
10 Correct 695 ms 14124 KB Output is correct
11 Correct 331 ms 14124 KB Output is correct
12 Correct 309 ms 14176 KB Output is correct
13 Correct 2 ms 14176 KB Output is correct
14 Correct 170 ms 14176 KB Output is correct
15 Correct 49 ms 14176 KB Output is correct
16 Correct 911 ms 14176 KB Output is correct
17 Correct 335 ms 14176 KB Output is correct
18 Correct 326 ms 14176 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 14176 KB Output is correct
2 Correct 4 ms 14176 KB Output is correct
3 Correct 4 ms 14176 KB Output is correct
4 Correct 10 ms 14176 KB Output is correct
5 Correct 6 ms 14176 KB Output is correct
6 Correct 7 ms 14176 KB Output is correct
7 Correct 2 ms 14176 KB Output is correct
8 Correct 172 ms 14176 KB Output is correct
9 Correct 247 ms 14176 KB Output is correct
10 Correct 700 ms 14176 KB Output is correct
11 Correct 352 ms 14224 KB Output is correct
12 Correct 308 ms 14224 KB Output is correct
13 Correct 2 ms 14224 KB Output is correct
14 Correct 171 ms 14224 KB Output is correct
15 Correct 49 ms 14224 KB Output is correct
16 Correct 896 ms 14224 KB Output is correct
17 Correct 329 ms 14224 KB Output is correct
18 Correct 327 ms 14224 KB Output is correct
19 Runtime error 226 ms 40800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -