oj.uz

Submission #935162

# Submission time Handle Problem Language Result Execution time Memory
935162 2024-02-28T18:09:37 Z zhasyn Wall (IOI14_wall) C++14
100 / 100
 564 ms 84160 KB 
#include <bits/stdc++.h>
#include <wall.h>
#define pii pair <int, int>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 8 * 1e6 + 10;
int over[N];
struct segtree {
	vector <pii> tree;
	vector <int> orin;
	int sz;
	void init(int n){
		sz = 1;
		while(sz < n) sz *= 2;
		tree.assign(2 * sz - 1, {-1, INT_MAX});
		orin.assign(2 * sz - 1, 0);
	}
	void make(int x, int nt){
		//cout << x << " was\n";
		//cout << tree[x].F << " "<< tree[x].S << " "<< orin[x] << endl;
		//cout << tree[nt].F << " "<< tree[nt].S << " "<< orin[x] << endl;
		if(tree[x].F >= tree[nt].S){
			tree[nt] = tree[x];
			orin[nt] = 1;	
		} else{
			if(tree[x].S <= tree[nt].F){
				tree[nt] = tree[x];
				orin[nt] = 2;
			} else{
				tree[nt].F = max(tree[nt].F, tree[x].F);
				tree[nt].S = min(tree[nt].S, tree[x].S);
			}
		}
		//cout << tree[nt].F << " " << tree[nt].S << " " << orin[nt] << endl;
	}
	
	void prop(int x, int lx, int rx){
		if(rx - lx == 1) return;
		if(orin[x] != 0){
			orin[2 * x + 1] = orin[2 * x + 2] = orin[x];
			tree[2 * x + 1] = tree[2 * x + 2] = tree[x];
		} else{
			make(x, 2 * x + 1);
			make(x, 2 * x + 2);
		}
		
		orin[x] = 0;
		tree[x] = {-1, INT_MAX};
	}
	void upd(int l, int r, int code, int val, int x, int lx, int rx){
		if(l >= rx || lx >= r) return;
		if(l <= lx && rx <= r){
			//cout << tree[x].F << " " << tree[x].S << " " << orin[x] << endl;
			if((code == 1 && val >= tree[x].S) || (code == 2 && val <= tree[x].F)){
				orin[x] = code;
				if(code == 1) tree[x] = {val, INT_MAX};
				else tree[x] = {-1, val};
			} else{
				if(code == 1 && orin[x] <= 1) tree[x].F = max(tree[x].F, val);
				if(code == 2 && (orin[x] == 0 || orin[x] == 2)) tree[x].S = min(tree[x].S, val);
			}
			//cout << x << " "<< lx << " "<< rx << " "<< tree[x].F << " " << tree[x].S << " "<< orin[x] << endl;
			return;
		}
		prop(x, lx, rx);
		int mid = (lx + rx) / 2;
		upd(l, r, code, val, 2 * x + 1, lx, mid);
		upd(l, r, code, val, 2 * x + 2, mid, rx);
	}
	void upd(int l, int r, int code, int val){
		upd(l, r, code, val, 0, 0, sz);
	}
	void get(int x, int lx, int rx, pii nt, int ntt){
		if(ntt != 0){
			tree[x] = nt;
			orin[x] = ntt;
		} else{
			if(nt.F >= tree[x].S){
				tree[x] = nt;
				orin[x] = 1;
			} else{
				if(nt.S <= tree[x].F){
					tree[x] = nt;
					orin[x] = 2;
				} else{
					tree[x].F = max(tree[x].F, nt.F);
					tree[x].S = min(tree[x].S, nt.S);
				}
			}
		}
		if(rx - lx == 1){
			//if(orin[x] == 0) over[lx] = -1;
			if(orin[x] <= 1) over[lx] = max(0, tree[x].F);
			if(orin[x] == 2) over[lx] = tree[x].S;
			return;
		}
		int mid = (lx + rx) / 2;
		get(2 * x + 1, lx, mid, tree[x], orin[x]);
		get(2 * x + 2, mid, rx, tree[x], orin[x]);
	}
	void get(){
		get(0, 0, sz, {-1, INT_MAX}, 0);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[],
int h[], int ans[]){
	for(int i = 0; i < n; i++){
		ans[i] = 0;
	}
	segtree obj;
	obj.init(n);
	for(int i = 0; i < k; i++){
		obj.upd(left[i], right[i] + 1, op[i], h[i]);
		//cout << endl;
	}
	obj.get();
	for(int i = 0; i < n; i++){
		ans[i] = over[i];
	}
}
// int main (){
	// int n, k;
	// cin >> n >> k;
	// int op[k], left[k], right[k], h[k], ans[n];
	// for(int i = 0; i < k; i++){
		// cin >> op[i] >> left[i] >> right[i] >> h[i];
	// }
	// buildWall(n, k, op, left, right, h, ans);
	// for(int i = 0; i < n; i++){
		// cout << ans[i] << " ";
	// }
	// return 0;
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 107 ms 8276 KB Output is correct
3 Correct 136 ms 4420 KB Output is correct
4 Correct 363 ms 13800 KB Output is correct
5 Correct 219 ms 13904 KB Output is correct
6 Correct 214 ms 13904 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 106 ms 8104 KB Output is correct
9 Correct 133 ms 4572 KB Output is correct
10 Correct 351 ms 13904 KB Output is correct
11 Correct 221 ms 13768 KB Output is correct
12 Correct 222 ms 13812 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 110 ms 8152 KB Output is correct
15 Correct 23 ms 1784 KB Output is correct
16 Correct 359 ms 13796 KB Output is correct
17 Correct 228 ms 13904 KB Output is correct
18 Correct 224 ms 13920 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 992 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 107 ms 8272 KB Output is correct
9 Correct 131 ms 4428 KB Output is correct
10 Correct 358 ms 13796 KB Output is correct
11 Correct 226 ms 13928 KB Output is correct
12 Correct 219 ms 13904 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 111 ms 8112 KB Output is correct
15 Correct 22 ms 1884 KB Output is correct
16 Correct 354 ms 13816 KB Output is correct
17 Correct 229 ms 13796 KB Output is correct
18 Correct 233 ms 13904 KB Output is correct
19 Correct 523 ms 73548 KB Output is correct
20 Correct 526 ms 83976 KB Output is correct
21 Correct 520 ms 84160 KB Output is correct
22 Correct 564 ms 83920 KB Output is correct
23 Correct 513 ms 84056 KB Output is correct
24 Correct 511 ms 84048 KB Output is correct
25 Correct 511 ms 84048 KB Output is correct
26 Correct 557 ms 84052 KB Output is correct
27 Correct 528 ms 84048 KB Output is correct
28 Correct 535 ms 83796 KB Output is correct
29 Correct 547 ms 84048 KB Output is correct
30 Correct 524 ms 83976 KB Output is correct