oj.uz

Submission #97257

# Submission time Handle Problem Language Result Execution time Memory
97257 2019-02-14T16:11:52 Z figter001 Wall (IOI14_wall) C++14
100 / 100
 1670 ms 69624 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = (1<<22);

int mx[maxn],mn[maxn];
int l,r,val,t;

void pro(int n){
	if(t == 1){
		mx[n] = max(mx[n],val);
		mn[n] = max(mn[n],val);
	}else{
		mx[n] = min(mx[n],val);
		mn[n] = min(mn[n],val);
	}
}

void pro(int n,int s,int e){
	mn[n] = min(mn[n],mn[n/2]);
	mn[n] = max(mn[n],mx[n/2]);
	mx[n] = max(mx[n],mx[n/2]);
	mx[n] = min(mx[n],mn[n/2]);
}

void update(int n,int s,int e){
	if(s > r || e < l)return;
	if(s >= l && e <= r){
		pro(n);
		return;
	}
	pro(n*2,s,e);
	pro(n*2+1,s,e);
	mn[n] = 1e9;
	mx[n] = 0;
	update(n*2,s,(s+e)/2);
	update(n*2+1,(s+e)/2+1,e);
}

int get(int n,int s,int e){
	if(s > r || e < l)return -1;
	if(s == e)return min(mn[n],mx[n]);
	pro(n*2,s,e);
	pro(n*2+1,s,e);
	mn[n] = 1e9;
	mx[n] = 0;
	return max(get(n*2,s,(s+e)/2) , get(n*2+1,(s+e)/2+1,e));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<maxn;i++)mn[i] = 1e9;
	for(int i=0;i<k;i++){
		left[i]++;
		right[i]++;
		l = left[i];
		r = right[i];
		val = height[i];
		t = op[i];
		update(1,1,n);
	}
	for(int i=0;i<n;i++){
		l = r = i+1;
		finalHeight[i] = get(1,1,n);
	}
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16768 KB Output is correct
2 Correct 20 ms 16896 KB Output is correct
3 Correct 17 ms 16768 KB Output is correct
4 Correct 23 ms 17152 KB Output is correct
5 Correct 27 ms 17144 KB Output is correct
6 Correct 26 ms 17152 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16768 KB Output is correct
2 Correct 198 ms 30360 KB Output is correct
3 Correct 197 ms 24184 KB Output is correct
4 Correct 668 ms 35992 KB Output is correct
5 Correct 382 ms 36984 KB Output is correct
6 Correct 442 ms 35292 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16896 KB Output is correct
2 Correct 20 ms 16896 KB Output is correct
3 Correct 20 ms 16768 KB Output is correct
4 Correct 24 ms 17144 KB Output is correct
5 Correct 26 ms 17152 KB Output is correct
6 Correct 21 ms 17188 KB Output is correct
7 Correct 19 ms 16812 KB Output is correct
8 Correct 269 ms 30540 KB Output is correct
9 Correct 307 ms 24316 KB Output is correct
10 Correct 690 ms 35824 KB Output is correct
11 Correct 552 ms 36920 KB Output is correct
12 Correct 453 ms 35328 KB Output is correct
13 Correct 18 ms 16768 KB Output is correct
14 Correct 285 ms 30516 KB Output is correct
15 Correct 64 ms 18168 KB Output is correct
16 Correct 688 ms 36120 KB Output is correct
17 Correct 387 ms 35576 KB Output is correct
18 Correct 366 ms 35576 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16764 KB Output is correct
2 Correct 20 ms 16888 KB Output is correct
3 Correct 20 ms 16768 KB Output is correct
4 Correct 27 ms 17144 KB Output is correct
5 Correct 26 ms 17172 KB Output is correct
6 Correct 23 ms 17148 KB Output is correct
7 Correct 17 ms 16768 KB Output is correct
8 Correct 221 ms 30584 KB Output is correct
9 Correct 237 ms 24244 KB Output is correct
10 Correct 650 ms 35884 KB Output is correct
11 Correct 526 ms 36856 KB Output is correct
12 Correct 534 ms 35320 KB Output is correct
13 Correct 18 ms 16768 KB Output is correct
14 Correct 226 ms 30460 KB Output is correct
15 Correct 59 ms 18296 KB Output is correct
16 Correct 703 ms 36128 KB Output is correct
17 Correct 387 ms 35576 KB Output is correct
18 Correct 411 ms 35468 KB Output is correct
19 Correct 1617 ms 69392 KB Output is correct
20 Correct 1607 ms 66884 KB Output is correct
21 Correct 1629 ms 69624 KB Output is correct
22 Correct 1550 ms 67096 KB Output is correct
23 Correct 1382 ms 66936 KB Output is correct
24 Correct 1401 ms 66980 KB Output is correct
25 Correct 1631 ms 66984 KB Output is correct
26 Correct 1402 ms 69392 KB Output is correct
27 Correct 1335 ms 69464 KB Output is correct
28 Correct 1542 ms 66936 KB Output is correct
29 Correct 1670 ms 66856 KB Output is correct
30 Correct 1372 ms 67048 KB Output is correct