oj.uz

Submission #774331

# Submission time Handle Problem Language Result Execution time Memory
774331 2023-07-05T15:16:59 Z phoenix0423 Wall (IOI14_wall) C++17
100 / 100
 1058 ms 224588 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
typedef tuple<ll, ll, ll> tll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define v vector
#define ckmax(a, b) a = max(a, b)
#define ckmin(a, b) a = min(a, b)
#define fastio ios::sync_with_stdio(false), cin.tie(0)
const int N = 1e9 + 7;
const int maxn = 2e6 + 5;
#pragma GCC optimize("Ofast")
int n;
struct Tag{
	ll l, r, alive;
	Tag(){alive = 0;}
	Tag(ll _l, ll _r) : l(_l), r(_r), alive(1){}
};
struct node{
	Tag tag;
	node(){}
};
node st[maxn * 4];
Tag cast(Tag a, Tag b){
	if(a.alive + b.alive < 2) return (a.alive ? a : b);
	if(a.l < b.l) a.l = b.l;
	else if(a.l > b.r) a.l = b.r;
	if(a.r > b.r) a.r = b.r;
	else if(a.r < b.l) a.r = b.l;
	return a;
}
void push(int v){
	st[v * 2].tag = cast(st[v * 2].tag, st[v].tag);
	st[v * 2 + 1].tag = cast(st[v * 2 + 1].tag, st[v].tag);
	st[v].tag = Tag();
}
void upd(int op, int l, int r, ll h, int v = 1, int L = 0, int R = n - 1){
	if(l > R || r < L) return;
	if(l <= L && r >= R){
		if(op == 1) st[v].tag = cast(st[v].tag, Tag(h, 1e18));
		else st[v].tag = cast(st[v].tag, Tag(0, h));
		return;
	}			
	push(v);
	int m = (L + R) / 2;
	upd(op, l, r, h, v * 2, L, m);
	upd(op, l, r, h, v * 2 + 1, m + 1, R);
}

ll qry(int pos, int v = 1, int l = 0, int r = n - 1){
	if(l == r) return st[v].tag.l;
	push(v);
	int m = (l + r) / 2;
	if(pos <= m) return qry(pos, v * 2, l, m);
	else return qry(pos, v * 2 + 1, m + 1, r);
}
void buildWall(int siz, int k, int op[], int l[], int r[], int h[], int ret[]){
	n = siz;
	for(int i = 0; i < k; i++){
		upd(op[i], l[i], r[i], h[i]);
	}
	for(int i = 0; i < n; i++){
		ret[i] = qry(i);
	}
}
/*
void solve(){
	int n, k;
	cin>>n>>k;
	vector<int> op(k), left(k), right(k), height(k), finalheight(n);
	for(int i = 0; i < k; i++){
		cin>>op[i]>>left[i]>>right[i]>>height[i];
	}
	buildWall(n, k, op, left, right, height, finalheight);
	for(int i = 0; i < n; i++) cout<<finalheight[i]<<" ";
	cout<<"\n";
}

int main(void){
	fastio;
	// freopen("balancing.in", "r", stdin);
	// freopen("balancing.out", "w", stdout);
	int t = 1;
	// cin>>t;
	while(t--){
		solve();
	}
}*/
/*
10 6 
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 188108 KB Output is correct
2 Correct 70 ms 188192 KB Output is correct
3 Correct 69 ms 188104 KB Output is correct
4 Correct 103 ms 188324 KB Output is correct
5 Correct 74 ms 188284 KB Output is correct
6 Correct 73 ms 188364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 188092 KB Output is correct
2 Correct 196 ms 201820 KB Output is correct
3 Correct 275 ms 195260 KB Output is correct
4 Correct 649 ms 206156 KB Output is correct
5 Correct 339 ms 207172 KB Output is correct
6 Correct 353 ms 205628 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 188108 KB Output is correct
2 Correct 73 ms 188292 KB Output is correct
3 Correct 74 ms 188180 KB Output is correct
4 Correct 81 ms 188288 KB Output is correct
5 Correct 79 ms 188300 KB Output is correct
6 Correct 77 ms 188376 KB Output is correct
7 Correct 75 ms 188112 KB Output is correct
8 Correct 183 ms 201804 KB Output is correct
9 Correct 270 ms 195276 KB Output is correct
10 Correct 683 ms 206112 KB Output is correct
11 Correct 354 ms 207228 KB Output is correct
12 Correct 340 ms 205652 KB Output is correct
13 Correct 83 ms 188204 KB Output is correct
14 Correct 189 ms 201792 KB Output is correct
15 Correct 102 ms 189332 KB Output is correct
16 Correct 673 ms 206372 KB Output is correct
17 Correct 343 ms 205740 KB Output is correct
18 Correct 342 ms 205740 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 188108 KB Output is correct
2 Correct 73 ms 188276 KB Output is correct
3 Correct 73 ms 188132 KB Output is correct
4 Correct 77 ms 188284 KB Output is correct
5 Correct 73 ms 188396 KB Output is correct
6 Correct 75 ms 188284 KB Output is correct
7 Correct 70 ms 188152 KB Output is correct
8 Correct 184 ms 201704 KB Output is correct
9 Correct 267 ms 195256 KB Output is correct
10 Correct 724 ms 206120 KB Output is correct
11 Correct 343 ms 207152 KB Output is correct
12 Correct 349 ms 205736 KB Output is correct
13 Correct 73 ms 188076 KB Output is correct
14 Correct 184 ms 201716 KB Output is correct
15 Correct 110 ms 189244 KB Output is correct
16 Correct 684 ms 206428 KB Output is correct
17 Correct 342 ms 205772 KB Output is correct
18 Correct 342 ms 205840 KB Output is correct
19 Correct 1022 ms 224548 KB Output is correct
20 Correct 991 ms 221956 KB Output is correct
21 Correct 1008 ms 224512 KB Output is correct
22 Correct 1000 ms 222052 KB Output is correct
23 Correct 1032 ms 222052 KB Output is correct
24 Correct 1006 ms 222204 KB Output is correct
25 Correct 1008 ms 222012 KB Output is correct
26 Correct 1032 ms 224588 KB Output is correct
27 Correct 1058 ms 224516 KB Output is correct
28 Correct 1035 ms 222084 KB Output is correct
29 Correct 997 ms 222016 KB Output is correct
30 Correct 995 ms 222040 KB Output is correct