oj.uz

Submission #934618

# Submission time Handle Problem Language Result Execution time Memory
934618 2024-02-27T17:08:33 Z zhasyn Wall (IOI14_wall) C++14
0 / 100
 122 ms 8196 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, {0, INT_MAX});
		orin.assign(2 * sz - 1, 0);
	}
	void make(int x, int nt){
		if(tree[x].F >= tree[nt].S){
			tree[nt] = tree[x];
			orin[x] = 1;	
		} else{
			if(tree[x].S <= tree[nt].F){
				tree[nt] = tree[x];
				orin[x] = 2;
			} else{
				tree[nt].F = max(tree[nt].F, tree[x].F);
				tree[nt].S = min(tree[nt].S, tree[x].S);
			}
		}
	}
	
	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] = {0, 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){
			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] = {0, val};
			} else{
				if(code == 1) tree[x].F = max(tree[x].F, val);
				else tree[x].S = min(tree[x].S, val);
			}
			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(orin[x] == 0){
				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);
					}
				}
			}
		}
		//cout << x << " "<< lx << " "<< rx << " " << local[x] << " " << cur[x].F << " "<< cur[x].S << endl;
		if(rx - lx == 1){
			//cout << orin[x] << " " << tree[x].F << endl;
			if(orin[x] <= 1) over[lx] = tree[x].F;
			else 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, {0, 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]);
	}
	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
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 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 97 ms 8196 KB Output is correct
3 Incorrect 122 ms 4656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

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 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -