oj.uz

Submission #538602

# Submission time Handle Problem Language Result Execution time Memory
538602 2022-03-17T08:14:09 Z Cantfindme Wall (IOI14_wall) C++17
100 / 100
 817 ms 232432 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 2000010;
const int INF = INT_MAX/4;
const int mod = 1e9+7;

int ans[maxn];

struct node {
	int s, m, e;
	int maxv= INF, minv=0;
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e; m = (s+e)/2;
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}

	void calc(int type, int x) {
		if (type == 0) { //minimise
			maxv = min(maxv, x);
			minv = min(minv, x);
		} else {
			minv = max(minv, x);
			maxv = max(maxv, x);
		}
	}

	void push() {
		// assert(s != e);
		if (minv != 0 and s != e) {
			l -> setmin(s, m, minv);
			r -> setmin(m+1, e, minv);
			minv = 0;
		}

		if (maxv != INF and s != e) {
			l -> setmax(s, m, maxv);
			r -> setmax(m+1, e, maxv);
			maxv = INF;
		}
	}

	void setmax(int x, int y, int nv) {
		if (s == x and e == y) {
			calc(0, nv);
		} else {
			push();
			if (x > m) r -> setmax(x,y, nv);
			else if (y <= m) l -> setmax(x,y,nv);
			else l -> setmax(x,m,nv), r -> setmax(m+1,y,nv);
		}
	}

	void setmin(int x, int y, int nv) {
		if (s == x and e == y) {
			calc(1, nv);
		} else {
			push();
			if (x > m) r -> setmin(x,y, nv);
			else if (y <= m) l -> setmin(x,y,nv);
			else l -> setmin(x,m,nv), r -> setmin(m+1,y,nv);
		}
	}

	void rmq() {
		// cout << s << " "  << e << " " << minv << " " << maxv << "\n";
		if (s == e) ans[s] = minv;
		else {
			push();
			l -> rmq();
			r -> rmq();
		}
	}
}*root;


void buildWall(int n, int Q, int op[], int left[], int right[], int height[], int finalHeight[]){

	root = new node(0,n-1);

	for (int q = 0; q < Q; q++) {
		int t = op[q];
		int l = left[q];
		int r = right[q];
		int h = height[q];
		if (t == 1) { //adding -> set min
			root -> setmin(l,r,h);
		} else {
			root -> setmax(l,r,h);
		}

		// root -> rmq();
		// for (int i = 0; i< n;i++) cout <<ans[i] << " ";
		// cout << "\n";
	}

	root -> rmq();
	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 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1364 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 132 ms 8104 KB Output is correct
3 Correct 222 ms 5564 KB Output is correct
4 Correct 701 ms 18432 KB Output is correct
5 Correct 232 ms 19016 KB Output is correct
6 Correct 219 ms 19020 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1364 KB Output is correct
5 Correct 5 ms 1356 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 147 ms 8024 KB Output is correct
9 Correct 180 ms 5408 KB Output is correct
10 Correct 703 ms 18512 KB Output is correct
11 Correct 211 ms 18980 KB Output is correct
12 Correct 210 ms 19036 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 141 ms 8108 KB Output is correct
15 Correct 34 ms 2528 KB Output is correct
16 Correct 800 ms 18684 KB Output is correct
17 Correct 229 ms 18648 KB Output is correct
18 Correct 221 ms 18756 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1364 KB Output is correct
5 Correct 4 ms 1364 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 145 ms 8112 KB Output is correct
9 Correct 196 ms 5444 KB Output is correct
10 Correct 666 ms 18412 KB Output is correct
11 Correct 229 ms 18948 KB Output is correct
12 Correct 199 ms 18904 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 161 ms 8068 KB Output is correct
15 Correct 39 ms 2508 KB Output is correct
16 Correct 801 ms 18712 KB Output is correct
17 Correct 271 ms 18700 KB Output is correct
18 Correct 215 ms 18676 KB Output is correct
19 Correct 817 ms 232324 KB Output is correct
20 Correct 754 ms 229860 KB Output is correct
21 Correct 771 ms 232432 KB Output is correct
22 Correct 738 ms 229760 KB Output is correct
23 Correct 753 ms 229828 KB Output is correct
24 Correct 761 ms 229828 KB Output is correct
25 Correct 745 ms 229812 KB Output is correct
26 Correct 753 ms 232312 KB Output is correct
27 Correct 764 ms 232144 KB Output is correct
28 Correct 766 ms 229524 KB Output is correct
29 Correct 743 ms 229620 KB Output is correct
30 Correct 748 ms 229580 KB Output is correct