oj.uz

Submission #203073

# Submission time Handle Problem Language Result Execution time Memory
203073 2020-02-19T08:21:00 Z detaomega Wall (IOI14_wall) C++14
100 / 100
 1024 ms 126840 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define de(x,y) cout<<#x<<" :"<<x<<y;
//#define int long long
#define SZ(xx) ((int)xx.size())
#define lowbit(xx) (xx&(-xx))
#define pb push_back
#define ls node*2
#define rs node*2+1
typedef pair<int,int> pii;
 
const int maxn = 3e6+5;
const int INF = 1e9+5;
int mx[maxn * 4], mn[maxn * 4], tag[maxn * 4], ans[maxn];
void ppush(int node) {
	mx[ls] = max(mx[ls], mx[node]);
	mx[rs] = max(mx[rs], mx[node]);
	mn[ls] = min(mn[ls], mn[node]);
	mn[rs] = min(mn[rs], mn[node]);
}
void push(int node) {
	if(mn[ls] != INF) {
		ppush(ls);
		mx[ls] = min(mx[ls], mn[ls]);
	}
	if(mn[rs] != INF) {
		ppush(rs);
		mx[rs] = min(mx[rs], mn[rs]);
	}
	if(tag[node]) {
		tag[rs] = tag[ls] = 1;
		mn[rs] = mn[ls] = INF;
	} 
	mx[ls] = max(mx[ls], mx[node]);
	mx[rs] = max(mx[rs], mx[node]);
	mn[ls] = min(mn[ls], mn[node]);
	mn[rs] = min(mn[rs], mn[node]);
	mx[node] = 0;
	mn[node] = INF;
	tag[node] = 0;
}
 
void upd(int node,int l,int r,int a,int b,int type,int val) {
	if(l != r)push(node);
	if(a <= l && r <= b) {
		if(type == 1) {
			if(mn[node] != INF)
				mx[node] = min(mn[node], mx[node]);
			tag[node] = 1;
			mn[node] = INF;
			mx[node] = max(mx[node], val);
		}
		else {
			tag[node] = 0;
			mn[node] = min(mn[node], val);
			mx[node] = min(mx[node], mn[node]);
		}
	}	
	else {
		
		int m = (l + r) >> 1;
		if(a <= m) upd(ls, l, m, a, b, type, val);
		if(b > m) upd(rs, m+1, r, a, b, type, val);
	}
}
 
void travel(int node,int l,int r) {
	if(l == r) {
		if(mn[node] != INF)
			ans[l] = min(mn[node], mx[node]);
		else
			ans[l] = mx[node];	
	}
	else {
		push(node);
		int m = (l + r) >> 1;
		travel(ls, l, m);
		travel(rs, m+1, r);
	}
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=1; i<=n * 2+10; i++) {
		mx[i] = 0;
		mn[i] = INF;
		tag[i] = 1; 
	}
	for(int i=0; i<k; i++) {
		upd(1, 1, n, left[i]+1, right[i]+1, op[i], height[i]);
	}
	travel(1, 1, n);
	for(int j=1; j<=n; j++) {
		finalHeight[j-1] =  ans[j];
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 12 ms 1216 KB Output is correct
5 Correct 11 ms 1272 KB Output is correct
6 Correct 11 ms 1272 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 181 ms 8312 KB Output is correct
3 Correct 204 ms 5112 KB Output is correct
4 Correct 748 ms 15352 KB Output is correct
5 Correct 330 ms 14584 KB Output is correct
6 Correct 317 ms 14632 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 13 ms 1272 KB Output is correct
5 Correct 12 ms 1272 KB Output is correct
6 Correct 12 ms 1272 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 188 ms 13944 KB Output is correct
9 Correct 214 ms 8872 KB Output is correct
10 Correct 739 ms 23928 KB Output is correct
11 Correct 337 ms 23928 KB Output is correct
12 Correct 319 ms 22504 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 189 ms 13944 KB Output is correct
15 Correct 47 ms 2936 KB Output is correct
16 Correct 808 ms 24184 KB Output is correct
17 Correct 352 ms 23544 KB Output is correct
18 Correct 337 ms 23672 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 12 ms 1272 KB Output is correct
5 Correct 11 ms 1272 KB Output is correct
6 Correct 11 ms 1272 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 223 ms 14072 KB Output is correct
9 Correct 202 ms 8824 KB Output is correct
10 Correct 784 ms 23928 KB Output is correct
11 Correct 345 ms 24104 KB Output is correct
12 Correct 321 ms 22392 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 190 ms 14072 KB Output is correct
15 Correct 47 ms 2932 KB Output is correct
16 Correct 792 ms 24184 KB Output is correct
17 Correct 346 ms 23672 KB Output is correct
18 Correct 348 ms 23672 KB Output is correct
19 Correct 983 ms 126768 KB Output is correct
20 Correct 962 ms 124408 KB Output is correct
21 Correct 971 ms 126712 KB Output is correct
22 Correct 993 ms 124280 KB Output is correct
23 Correct 970 ms 124236 KB Output is correct
24 Correct 994 ms 124368 KB Output is correct
25 Correct 976 ms 124412 KB Output is correct
26 Correct 1024 ms 126708 KB Output is correct
27 Correct 987 ms 126840 KB Output is correct
28 Correct 976 ms 124280 KB Output is correct
29 Correct 982 ms 124152 KB Output is correct
30 Correct 988 ms 124152 KB Output is correct