Submission #73653

# Submission time Handle Problem Language Result Execution time Memory
73653 2018-08-28T16:23:52 Z TuGSGeReL Wall (IOI14_wall) C++14
100 / 100
1012 ms 179712 KB
#include "wall.h"
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back
#define ss second
#define ff first
#define ext exit(0)
using namespace std;
int o,a[2000001],lax[6000001],lam[6000001],fin[2000001];
void init(int node, int l , int r){
	lam[node]=INT_MAX;
	lax[node]=0;
	if(l==r) return;
	int mid=(l+r)/2;
	init(node*2,l,mid);
	init(node*2+1,mid+1,r);
}
void mx(int node, int h){
	lax[node]=max(lax[node],h);
	lam[node]=max(lam[node],lax[node]);
}
void mn(int node, int h){
	lam[node]=min(lam[node],h);
	lax[node]=min(lax[node],lam[node]);
}
void push(int node){
	mx(node*2,lax[node]);
	mx(node*2+1,lax[node]);
	mn(node*2,lam[node]);
	mn(node*2+1,lam[node]);
	lax[node]=0;
	lam[node]=INT_MAX;
}
void query(int node,int l , int r, int L , int R, int h, int o){
	if(l>R || r< L) return;
	if(l>=L && r<=R) {
		if(o==1)mx(node,h);
		else mn(node,h);
		return ;
	}
	push(node);
	int mid=(l+r)/2;
	query(node*2,l,mid,L,R,h,o);
	query(node*2+1,mid+1,r,L,R,h,o);
}
void f(int node, int l , int r){
	if(l==r){
		fin[l]=lax[node];
		return ;
	}
	push(node);
	int mid=(l+r)/2;
	f(node*2,l,mid);
	f(node*2+1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	init(1,0,n-1);
	for(int i=0;i<k;i++){
		query(1,0,n-1,left[i],right[i],height[i],op[i]);
	}
	f(1,0,n-1);
	for(int i=0;i<n;i++) finalHeight[i]=fin[i];
	return;
}
# Verdict Execution time Memory Grader output
1 Correct 4 ms 288 KB Output is correct
2 Correct 5 ms 484 KB Output is correct
3 Correct 5 ms 484 KB Output is correct
4 Correct 13 ms 800 KB Output is correct
5 Correct 14 ms 932 KB Output is correct
6 Correct 11 ms 932 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 932 KB Output is correct
2 Correct 253 ms 8432 KB Output is correct
3 Correct 329 ms 8432 KB Output is correct
4 Correct 860 ms 11464 KB Output is correct
5 Correct 424 ms 11920 KB Output is correct
6 Correct 459 ms 11996 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 11996 KB Output is correct
2 Correct 7 ms 11996 KB Output is correct
3 Correct 5 ms 11996 KB Output is correct
4 Correct 10 ms 11996 KB Output is correct
5 Correct 10 ms 11996 KB Output is correct
6 Correct 9 ms 11996 KB Output is correct
7 Correct 3 ms 11996 KB Output is correct
8 Correct 239 ms 11996 KB Output is correct
9 Correct 270 ms 11996 KB Output is correct
10 Correct 978 ms 11996 KB Output is correct
11 Correct 563 ms 12076 KB Output is correct
12 Correct 450 ms 12076 KB Output is correct
13 Correct 2 ms 12076 KB Output is correct
14 Correct 223 ms 12076 KB Output is correct
15 Correct 53 ms 12076 KB Output is correct
16 Correct 652 ms 12076 KB Output is correct
17 Correct 391 ms 12076 KB Output is correct
18 Correct 361 ms 12076 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 12076 KB Output is correct
2 Correct 4 ms 12076 KB Output is correct
3 Correct 4 ms 12076 KB Output is correct
4 Correct 9 ms 12076 KB Output is correct
5 Correct 12 ms 12076 KB Output is correct
6 Correct 8 ms 12076 KB Output is correct
7 Correct 2 ms 12076 KB Output is correct
8 Correct 181 ms 12076 KB Output is correct
9 Correct 208 ms 12076 KB Output is correct
10 Correct 669 ms 12076 KB Output is correct
11 Correct 360 ms 12084 KB Output is correct
12 Correct 436 ms 12236 KB Output is correct
13 Correct 3 ms 12236 KB Output is correct
14 Correct 246 ms 12236 KB Output is correct
15 Correct 46 ms 12236 KB Output is correct
16 Correct 728 ms 12236 KB Output is correct
17 Correct 367 ms 12236 KB Output is correct
18 Correct 472 ms 12236 KB Output is correct
19 Correct 919 ms 67024 KB Output is correct
20 Correct 860 ms 75212 KB Output is correct
21 Correct 833 ms 88252 KB Output is correct
22 Correct 934 ms 96164 KB Output is correct
23 Correct 979 ms 106584 KB Output is correct
24 Correct 915 ms 116844 KB Output is correct
25 Correct 976 ms 127332 KB Output is correct
26 Correct 1012 ms 140396 KB Output is correct
27 Correct 1006 ms 150720 KB Output is correct
28 Correct 880 ms 158876 KB Output is correct
29 Correct 881 ms 169168 KB Output is correct
30 Correct 893 ms 179712 KB Output is correct