oj.uz

Submission #88419

# Submission time Handle Problem Language Result Execution time Memory
88419 2018-12-05T18:46:33 Z Pajaraja Wall (IOI14_wall) C++17
61 / 100
 1002 ms 226272 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
int seg[4*MAXN],poz[MAXN];
bool tr[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]];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 628 KB Output is correct
3 Correct 4 ms 644 KB Output is correct
4 Correct 10 ms 1004 KB Output is correct
5 Correct 7 ms 1092 KB Output is correct
6 Correct 7 ms 1384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1384 KB Output is correct
2 Correct 170 ms 14472 KB Output is correct
3 Correct 245 ms 14472 KB Output is correct
4 Correct 698 ms 30224 KB Output is correct
5 Correct 340 ms 40904 KB Output is correct
6 Correct 311 ms 49564 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 49564 KB Output is correct
2 Correct 3 ms 49564 KB Output is correct
3 Correct 4 ms 49564 KB Output is correct
4 Correct 10 ms 49564 KB Output is correct
5 Correct 7 ms 49564 KB Output is correct
6 Correct 7 ms 49564 KB Output is correct
7 Correct 2 ms 49564 KB Output is correct
8 Correct 171 ms 53100 KB Output is correct
9 Correct 247 ms 53100 KB Output is correct
10 Correct 705 ms 68880 KB Output is correct
11 Correct 334 ms 79472 KB Output is correct
12 Correct 311 ms 88036 KB Output is correct
13 Correct 2 ms 88036 KB Output is correct
14 Correct 176 ms 91240 KB Output is correct
15 Correct 54 ms 91240 KB Output is correct
16 Correct 925 ms 104012 KB Output is correct
17 Correct 336 ms 113028 KB Output is correct
18 Correct 332 ms 122068 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 122068 KB Output is correct
2 Correct 4 ms 122068 KB Output is correct
3 Correct 4 ms 122068 KB Output is correct
4 Correct 10 ms 122068 KB Output is correct
5 Correct 7 ms 122068 KB Output is correct
6 Correct 7 ms 122068 KB Output is correct
7 Correct 2 ms 122068 KB Output is correct
8 Correct 175 ms 125776 KB Output is correct
9 Correct 252 ms 125776 KB Output is correct
10 Correct 707 ms 141444 KB Output is correct
11 Correct 341 ms 152064 KB Output is correct
12 Correct 314 ms 160860 KB Output is correct
13 Correct 2 ms 160860 KB Output is correct
14 Correct 174 ms 163728 KB Output is correct
15 Correct 49 ms 163728 KB Output is correct
16 Correct 1002 ms 176524 KB Output is correct
17 Correct 332 ms 185620 KB Output is correct
18 Correct 325 ms 194540 KB Output is correct
19 Runtime error 227 ms 226272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -