oj.uz

Submission #73652

# Submission time Handle Problem Language Result Execution time Memory
73652 2018-08-28T16:21:57 Z TuGSGeReL Wall (IOI14_wall) C++14
61 / 100
 922 ms 67148 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[4000001],lam[4000001],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;
}

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 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 15 ms 940 KB Output is correct
5 Correct 9 ms 940 KB Output is correct
6 Correct 8 ms 940 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 940 KB Output is correct
2 Correct 186 ms 8320 KB Output is correct
3 Correct 280 ms 8320 KB Output is correct
4 Correct 802 ms 11424 KB Output is correct
5 Correct 415 ms 12160 KB Output is correct
6 Correct 371 ms 12160 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12160 KB Output is correct
2 Correct 4 ms 12160 KB Output is correct
3 Correct 4 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 8 ms 12160 KB Output is correct
7 Correct 2 ms 12160 KB Output is correct
8 Correct 219 ms 12160 KB Output is correct
9 Correct 217 ms 12160 KB Output is correct
10 Correct 683 ms 12160 KB Output is correct
11 Correct 387 ms 12160 KB Output is correct
12 Correct 393 ms 12160 KB Output is correct
13 Correct 2 ms 12160 KB Output is correct
14 Correct 185 ms 12160 KB Output is correct
15 Correct 50 ms 12160 KB Output is correct
16 Correct 683 ms 12160 KB Output is correct
17 Correct 339 ms 12160 KB Output is correct
18 Correct 431 ms 12160 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12160 KB Output is correct
2 Correct 7 ms 12160 KB Output is correct
3 Correct 5 ms 12160 KB Output is correct
4 Correct 9 ms 12160 KB Output is correct
5 Correct 10 ms 12160 KB Output is correct
6 Correct 10 ms 12160 KB Output is correct
7 Correct 2 ms 12160 KB Output is correct
8 Correct 199 ms 12160 KB Output is correct
9 Correct 245 ms 12160 KB Output is correct
10 Correct 649 ms 12160 KB Output is correct
11 Correct 430 ms 12160 KB Output is correct
12 Correct 430 ms 12204 KB Output is correct
13 Correct 2 ms 12204 KB Output is correct
14 Correct 202 ms 12204 KB Output is correct
15 Correct 45 ms 12204 KB Output is correct
16 Correct 811 ms 12204 KB Output is correct
17 Correct 414 ms 12204 KB Output is correct
18 Correct 432 ms 12204 KB Output is correct
19 Incorrect 922 ms 67148 KB Output isn't correct
20 Halted 0 ms 0 KB -