oj.uz

Submission #703199

# Submission time Handle Problem Language Result Execution time Memory
703199 2023-02-26T14:22:56 Z bane Wall (IOI14_wall) C++17
100 / 100
 1651 ms 224560 KB 
#include<bits/stdc++.h>
#include<wall.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define ll long long 
 
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
const int EX = (int)-1e9;
const int MAXN = 2000000*3;
pair<ll,ll> t[MAXN];
pair<ll,ll> lazy[MAXN]; //{max,min}
int n;
void propagate(int k, int l, int r){
	{
			t[k].fr = max(t[k].fr, lazy[k].fr);
			t[k].sc = max(t[k].sc, t[k].fr);
			if (l != r){
				lazy[k*2].fr = max(lazy[k*2].fr, lazy[k].fr);
				lazy[k*2].sc = max(lazy[k*2].sc, lazy[k*2].fr);
				lazy[k*2+1].fr = max(lazy[k*2+1].fr, lazy[k].fr);
				lazy[k*2+1].sc = max(lazy[k*2+1].sc, lazy[k*2+1].fr);
			}
			lazy[k].fr = EX;
	}
	{
		t[k].sc = min(t[k].sc, lazy[k].sc);
		t[k].fr = min(t[k].fr, t[k].sc);
		if (l!=r){
			lazy[k*2].sc = min(lazy[k*2].sc, lazy[k].sc);
			lazy[k*2].fr = min(lazy[k*2].fr, lazy[k*2].sc);
			lazy[k*2+1].sc = min(lazy[k*2+1].sc, lazy[k].sc);
			lazy[k*2+1].fr = min(lazy[k*2+1].fr, lazy[k*2+1].sc);
		}
		lazy[k].sc = -EX;
	}
}
void update(int a, int b, int inc, int v, int l = 0, int r = n - 1, int k = 1){
	propagate(k,l,r);
	if (l > b || r < a)return;
	if (l >= a && r <= b){
		if (inc)lazy[k].fr = v;
		else lazy[k].sc=v;
		propagate(k,l,r);
		return;
	}
	update(a,b,inc,v,l,(l+r)/2,k*2);
	update(a,b,inc,v,(l+r)/2+1,r,k*2+1);
}
int query(int a, int l = 0, int r = n - 1, int k=  1){
	propagate(k,l,r);
	if (l == r){
		return t[k].fr;
	}
	int m = (l + r)/2;
	if (a <= m)return query(a,l,m,k*2);
	else return query(a,m+1,r,k*2+1);
}
void buildWall(int nn, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	n = nn;
	for (int i = 0; i < MAXN;i++){
		t[i] = {EX, -EX};
		lazy[i]= {EX,-EX};
	}
	for (int i = 0; i < k; ++i){
		update(left[i], right[i], (op[i] == 1), height[i]);
	}
	for (int i =0 ; i < n; ++i){
		finalHeight[i] = max(0, query(i));
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 188056 KB Output is correct
2 Correct 75 ms 188252 KB Output is correct
3 Correct 75 ms 188204 KB Output is correct
4 Correct 100 ms 188356 KB Output is correct
5 Correct 87 ms 188344 KB Output is correct
6 Correct 81 ms 188284 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 188128 KB Output is correct
2 Correct 212 ms 201764 KB Output is correct
3 Correct 319 ms 195268 KB Output is correct
4 Correct 846 ms 206144 KB Output is correct
5 Correct 499 ms 207192 KB Output is correct
6 Correct 496 ms 205644 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 188160 KB Output is correct
2 Correct 77 ms 188208 KB Output is correct
3 Correct 83 ms 188184 KB Output is correct
4 Correct 83 ms 188400 KB Output is correct
5 Correct 96 ms 188296 KB Output is correct
6 Correct 82 ms 188284 KB Output is correct
7 Correct 77 ms 188200 KB Output is correct
8 Correct 223 ms 201716 KB Output is correct
9 Correct 307 ms 195280 KB Output is correct
10 Correct 833 ms 206112 KB Output is correct
11 Correct 481 ms 207136 KB Output is correct
12 Correct 487 ms 205616 KB Output is correct
13 Correct 73 ms 188052 KB Output is correct
14 Correct 206 ms 201708 KB Output is correct
15 Correct 111 ms 189232 KB Output is correct
16 Correct 853 ms 206436 KB Output is correct
17 Correct 483 ms 205772 KB Output is correct
18 Correct 485 ms 205952 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 188148 KB Output is correct
2 Correct 74 ms 188212 KB Output is correct
3 Correct 74 ms 188168 KB Output is correct
4 Correct 85 ms 188364 KB Output is correct
5 Correct 94 ms 188320 KB Output is correct
6 Correct 82 ms 188292 KB Output is correct
7 Correct 75 ms 188108 KB Output is correct
8 Correct 215 ms 201804 KB Output is correct
9 Correct 312 ms 195228 KB Output is correct
10 Correct 846 ms 206148 KB Output is correct
11 Correct 491 ms 207180 KB Output is correct
12 Correct 482 ms 205668 KB Output is correct
13 Correct 76 ms 188024 KB Output is correct
14 Correct 215 ms 201780 KB Output is correct
15 Correct 122 ms 189332 KB Output is correct
16 Correct 821 ms 206488 KB Output is correct
17 Correct 480 ms 205800 KB Output is correct
18 Correct 486 ms 205828 KB Output is correct
19 Correct 1486 ms 224508 KB Output is correct
20 Correct 1464 ms 222064 KB Output is correct
21 Correct 1485 ms 224560 KB Output is correct
22 Correct 1530 ms 222044 KB Output is correct
23 Correct 1651 ms 221396 KB Output is correct
24 Correct 1623 ms 222004 KB Output is correct
25 Correct 1601 ms 221976 KB Output is correct
26 Correct 1625 ms 224512 KB Output is correct
27 Correct 1636 ms 224524 KB Output is correct
28 Correct 1614 ms 221980 KB Output is correct
29 Correct 1552 ms 221940 KB Output is correct
30 Correct 1490 ms 222016 KB Output is correct