oj.uz

Submission #935160

# Submission time Handle Problem Language Result Execution time Memory
935160 2024-02-28T18:08:17 Z zhasyn Wall (IOI14_wall) C++14
61 / 100
 446 ms 158292 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 = 2 * 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 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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 115 ms 11340 KB Output is correct
3 Correct 131 ms 6068 KB Output is correct
4 Correct 356 ms 23616 KB Output is correct
5 Correct 225 ms 23888 KB Output is correct
6 Correct 216 ms 22352 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 108 ms 13892 KB Output is correct
9 Correct 129 ms 8272 KB Output is correct
10 Correct 351 ms 23460 KB Output is correct
11 Correct 224 ms 23892 KB Output is correct
12 Correct 250 ms 22604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 113 ms 14028 KB Output is correct
15 Correct 22 ms 2380 KB Output is correct
16 Correct 370 ms 23404 KB Output is correct
17 Correct 231 ms 22820 KB Output is correct
18 Correct 225 ms 22868 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 928 KB Output is correct
5 Correct 4 ms 1044 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 109 ms 13908 KB Output is correct
9 Correct 129 ms 8276 KB Output is correct
10 Correct 352 ms 23376 KB Output is correct
11 Correct 229 ms 24068 KB Output is correct
12 Correct 223 ms 22768 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 110 ms 13908 KB Output is correct
15 Correct 22 ms 2396 KB Output is correct
16 Correct 366 ms 23404 KB Output is correct
17 Correct 227 ms 22864 KB Output is correct
18 Correct 234 ms 22868 KB Output is correct
19 Runtime error 446 ms 158292 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -