oj.uz

Submission #292821

# Submission time Handle Problem Language Result Execution time Memory
292821 2020-09-07T13:48:55 Z oolimry Wall (IOI14_wall) C++14
100 / 100
 1061 ms 232664 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;

const int inf = 1023456789;

vector<int> ans;

struct node{
	int s, e, m;
	int low, high;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s != e){
			low = 0, high = inf;
			l = new node(s, m);
			r = new node(m+1, e);
		}
		else low = 0, high = 0;
	}
	
	void apply(int L, int H){
		if(L > high) low = high = L;
		else if(H < low) low = high = H;
		else{
			low = max(low, L);
			high = min(high, H);
		}
	}
	
	void push(){
		if(s == e) return;
		l->apply(low, high);
		r->apply(low, high);
		low = 0, high = inf;
	}
		
	void update(int S, int E, int op, int H){
		push();
		if(S == s && E == e){
			if(op == 1) apply(H, inf);
			else if(op == 2) apply(-inf, H);
			return;
		}
		else if(E <= m) l->update(S, E, op, H);
		else if(S >= m+1) r->update(S, E, op, H);
		else{
			l->update(S, m, op, H);
			r->update(m+1, E, op, H);
		}
	}
	
	void out(){
		push();
		//cout << s << " " << e << ": " << "(" << low << ", " << high << ")\n";
		if(s == e){
			ans.push_back(low);
			return;
		}
		else{
			l->out();
			r->out();
		}
	}
} *root;

void buildWall(int n, int Q, int op[], int L[], int R[], int H[], int finalHeight[]){
	root = new node(0, n-1);
	for(int q = 0;q < Q;q++){
		root->update(L[q], R[q], op[q], H[q]);
	}
	root->out();
	for(int i = 0;i < n;i++) finalHeight[i] = ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1664 KB Output is correct
5 Correct 7 ms 1596 KB Output is correct
6 Correct 7 ms 1664 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 174 ms 14076 KB Output is correct
3 Correct 206 ms 9448 KB Output is correct
4 Correct 839 ms 28400 KB Output is correct
5 Correct 329 ms 29296 KB Output is correct
6 Correct 311 ms 27760 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 1664 KB Output is correct
5 Correct 7 ms 1664 KB Output is correct
6 Correct 7 ms 1664 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 175 ms 13932 KB Output is correct
9 Correct 202 ms 9464 KB Output is correct
10 Correct 776 ms 28272 KB Output is correct
11 Correct 327 ms 29296 KB Output is correct
12 Correct 303 ms 27760 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 169 ms 14128 KB Output is correct
15 Correct 42 ms 3320 KB Output is correct
16 Correct 964 ms 28496 KB Output is correct
17 Correct 323 ms 28020 KB Output is correct
18 Correct 316 ms 28016 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 9 ms 1664 KB Output is correct
5 Correct 7 ms 1664 KB Output is correct
6 Correct 7 ms 1664 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 169 ms 14072 KB Output is correct
9 Correct 207 ms 9336 KB Output is correct
10 Correct 787 ms 28232 KB Output is correct
11 Correct 326 ms 29296 KB Output is correct
12 Correct 309 ms 27760 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 170 ms 13944 KB Output is correct
15 Correct 43 ms 3320 KB Output is correct
16 Correct 970 ms 28528 KB Output is correct
17 Correct 323 ms 27916 KB Output is correct
18 Correct 318 ms 28016 KB Output is correct
19 Correct 1043 ms 232660 KB Output is correct
20 Correct 1035 ms 230108 KB Output is correct
21 Correct 1037 ms 232536 KB Output is correct
22 Correct 1061 ms 230112 KB Output is correct
23 Correct 1039 ms 230072 KB Output is correct
24 Correct 1053 ms 230224 KB Output is correct
25 Correct 1044 ms 230104 KB Output is correct
26 Correct 1054 ms 232592 KB Output is correct
27 Correct 1061 ms 232664 KB Output is correct
28 Correct 1032 ms 230104 KB Output is correct
29 Correct 1036 ms 230104 KB Output is correct
30 Correct 1042 ms 230104 KB Output is correct