oj.uz

Submission #203068

# Submission time Handle Problem Language Result Execution time Memory
203068 2020-02-19T07:47:03 Z detaomega Wall (IOI14_wall) C++14
24 / 100
 645 ms 22904 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 push(int node) {
	if(mn[ls] != INF) {
		mx[ls] = min(mx[ls], mn[ls]);
	}
	if(mn[rs] != INF) {
		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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Incorrect 6 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 192 ms 8188 KB Output is correct
3 Correct 207 ms 4600 KB Output is correct
4 Correct 645 ms 12280 KB Output is correct
5 Correct 336 ms 22904 KB Output is correct
6 Correct 310 ms 21368 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Incorrect 6 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
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 Incorrect 6 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -