oj.uz

Submission #287077

# Submission time Handle Problem Language Result Execution time Memory
287077 2020-08-31T11:30:21 Z theStaticMind Wall (IOI14_wall) C++14
100 / 100
 1106 ms 69624 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
using namespace std;

#include "wall.h"

const int S = (1 << (int)ceil(log2(2e6)));
vector<int> L(S*2, 0);
vector<int> R(S*2, INT_MAX);

void push(int j){
	if(j < S){
		if(L[j] == R[j]){
			L[j*2] = R[j*2] = L[j*2+1] = R[j*2+1] = L[j];
		}
		else{
			if(L[j*2] == R[j*2]){
				if(R[j] < L[j*2]) L[j*2] = R[j*2] = R[j];
				if(L[j] > L[j*2]) L[j*2] = R[j*2] = L[j];
			}
			else if(R[j] < L[j*2]){
				L[j*2] = R[j*2] = R[j];
			}
			else if(L[j] > R[j*2]){
				L[j*2] = R[j*2] = L[j];
			}
			else{
				R[j*2] = min(R[j*2], R[j]);
				L[j*2] = max(L[j*2], L[j]);
			}
			if(L[j*2+1] == R[j*2+1]){
				if(R[j] < L[j*2+1]) L[j*2+1] = R[j*2+1] = R[j];
				if(L[j] > L[j*2+1]) L[j*2+1] = R[j*2+1] = L[j];
			}
			else if(R[j] < L[j*2+1]){
				L[j*2+1] = R[j*2+1] = R[j];
			}
			else if(L[j] > R[j*2+1]){
				L[j*2+1] = R[j*2+1] = L[j];
			}
			else{
				R[j*2+1] = min(R[j*2+1], R[j]);
				L[j*2+1] = max(L[j*2+1], L[j]);
			}

		}
		L[j] = 0, R[j] = INT_MAX;
	}
}

void rangeupdate(int j, int x, int y, int l, int r, int t, int v){
	if(y < l || r < x) return;
	push(j);
	if(l <= x && y <= r){
		if(t == 1){
			L[j] = max(L[j], v);
			R[j] = max(R[j], v);
		}
		else{
			L[j] = min(L[j], v);
			R[j] = min(R[j], v);
		}
		return;
	}
	rangeupdate(j*2,x,(x+y)/2,l,r,t,v);
	rangeupdate(j*2+1,(x+y)/2+1,y,l,r,t,v);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0; i < k; i++){
		rangeupdate(1,0,S-1,left[i],right[i],op[i], height[i]);
	}
	for(int i = 1; i < S; i++) push(i);

	for(int i = 0; i < n; i++){
		finalHeight[i] = L[S + i];
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 33144 KB Output is correct
2 Correct 50 ms 33272 KB Output is correct
3 Correct 41 ms 33152 KB Output is correct
4 Correct 46 ms 33280 KB Output is correct
5 Correct 48 ms 33280 KB Output is correct
6 Correct 54 ms 33272 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 33152 KB Output is correct
2 Correct 497 ms 40952 KB Output is correct
3 Correct 353 ms 36564 KB Output is correct
4 Correct 820 ms 51312 KB Output is correct
5 Correct 529 ms 52472 KB Output is correct
6 Correct 504 ms 50680 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 33152 KB Output is correct
2 Correct 51 ms 33280 KB Output is correct
3 Correct 39 ms 33144 KB Output is correct
4 Correct 44 ms 33324 KB Output is correct
5 Correct 44 ms 33280 KB Output is correct
6 Correct 44 ms 33280 KB Output is correct
7 Correct 37 ms 33152 KB Output is correct
8 Correct 476 ms 41052 KB Output is correct
9 Correct 356 ms 36600 KB Output is correct
10 Correct 889 ms 51248 KB Output is correct
11 Correct 533 ms 52268 KB Output is correct
12 Correct 508 ms 50724 KB Output is correct
13 Correct 41 ms 33144 KB Output is correct
14 Correct 493 ms 46984 KB Output is correct
15 Correct 85 ms 34424 KB Output is correct
16 Correct 850 ms 51456 KB Output is correct
17 Correct 509 ms 50936 KB Output is correct
18 Correct 509 ms 50888 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 33152 KB Output is correct
2 Correct 40 ms 33280 KB Output is correct
3 Correct 41 ms 33144 KB Output is correct
4 Correct 46 ms 33280 KB Output is correct
5 Correct 57 ms 33324 KB Output is correct
6 Correct 44 ms 33280 KB Output is correct
7 Correct 38 ms 33152 KB Output is correct
8 Correct 476 ms 40952 KB Output is correct
9 Correct 337 ms 36600 KB Output is correct
10 Correct 863 ms 51204 KB Output is correct
11 Correct 625 ms 52344 KB Output is correct
12 Correct 535 ms 50808 KB Output is correct
13 Correct 47 ms 33152 KB Output is correct
14 Correct 477 ms 46968 KB Output is correct
15 Correct 84 ms 34368 KB Output is correct
16 Correct 859 ms 51576 KB Output is correct
17 Correct 567 ms 50936 KB Output is correct
18 Correct 513 ms 50936 KB Output is correct
19 Correct 1106 ms 69624 KB Output is correct
20 Correct 1022 ms 67192 KB Output is correct
21 Correct 1038 ms 69624 KB Output is correct
22 Correct 1010 ms 67120 KB Output is correct
23 Correct 1020 ms 67192 KB Output is correct
24 Correct 1022 ms 67204 KB Output is correct
25 Correct 1000 ms 67064 KB Output is correct
26 Correct 1010 ms 69624 KB Output is correct
27 Correct 1022 ms 69624 KB Output is correct
28 Correct 1010 ms 67132 KB Output is correct
29 Correct 1000 ms 67064 KB Output is correct
30 Correct 1025 ms 67192 KB Output is correct