oj.uz

Submission #741595

# Submission time Handle Problem Language Result Execution time Memory
741595 2023-05-14T12:45:17 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 1530 ms 214156 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 73 ms 188132 KB Output is correct
2 Correct 76 ms 188164 KB Output is correct
3 Correct 77 ms 188236 KB Output is correct
4 Correct 83 ms 188300 KB Output is correct
5 Correct 86 ms 188256 KB Output is correct
6 Correct 81 ms 188288 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 188092 KB Output is correct
2 Correct 216 ms 196088 KB Output is correct
3 Correct 325 ms 191488 KB Output is correct
4 Correct 917 ms 196520 KB Output is correct
5 Correct 480 ms 197084 KB Output is correct
6 Correct 497 ms 197068 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 188048 KB Output is correct
2 Correct 76 ms 188120 KB Output is correct
3 Correct 75 ms 188068 KB Output is correct
4 Correct 85 ms 188208 KB Output is correct
5 Correct 81 ms 188196 KB Output is correct
6 Correct 81 ms 188284 KB Output is correct
7 Correct 77 ms 188060 KB Output is correct
8 Correct 209 ms 196180 KB Output is correct
9 Correct 311 ms 191420 KB Output is correct
10 Correct 888 ms 196512 KB Output is correct
11 Correct 498 ms 197048 KB Output is correct
12 Correct 481 ms 197164 KB Output is correct
13 Correct 73 ms 188124 KB Output is correct
14 Correct 205 ms 195980 KB Output is correct
15 Correct 112 ms 188696 KB Output is correct
16 Correct 877 ms 196768 KB Output is correct
17 Correct 499 ms 196796 KB Output is correct
18 Correct 482 ms 196864 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 188108 KB Output is correct
2 Correct 75 ms 188160 KB Output is correct
3 Correct 78 ms 188132 KB Output is correct
4 Correct 86 ms 188240 KB Output is correct
5 Correct 87 ms 188212 KB Output is correct
6 Correct 79 ms 188236 KB Output is correct
7 Correct 75 ms 188080 KB Output is correct
8 Correct 248 ms 196044 KB Output is correct
9 Correct 315 ms 191516 KB Output is correct
10 Correct 802 ms 196556 KB Output is correct
11 Correct 490 ms 196964 KB Output is correct
12 Correct 474 ms 197020 KB Output is correct
13 Correct 75 ms 188056 KB Output is correct
14 Correct 206 ms 196000 KB Output is correct
15 Correct 117 ms 188772 KB Output is correct
16 Correct 842 ms 196884 KB Output is correct
17 Correct 497 ms 196764 KB Output is correct
18 Correct 479 ms 196768 KB Output is correct
19 Correct 1462 ms 214048 KB Output is correct
20 Correct 1465 ms 211624 KB Output is correct
21 Correct 1489 ms 214156 KB Output is correct
22 Correct 1468 ms 211548 KB Output is correct
23 Correct 1469 ms 211620 KB Output is correct
24 Correct 1468 ms 211612 KB Output is correct
25 Correct 1482 ms 211576 KB Output is correct
26 Correct 1498 ms 214028 KB Output is correct
27 Correct 1474 ms 214052 KB Output is correct
28 Correct 1530 ms 211564 KB Output is correct
29 Correct 1471 ms 211548 KB Output is correct
30 Correct 1475 ms 211532 KB Output is correct