oj.uz

Submission #684547

# Submission time Handle Problem Language Result Execution time Memory
684547 2023-01-21T16:49:05 Z fuad27 Wall (IOI14_wall) C++17
100 / 100
 1878 ms 99396 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif

const int N = 2000010;
pair<int,int> T[4*N];
void updMn(int l, int r, int tl, int tr, int v, int p, int d);
void updMx(int l, int r, int tl, int tr, int v, int p, int d);
void updMn(int l, int r, int tl, int tr, int v, int p, int d=0) {
	if(l>r)return;
	if(l==tl and r==tr) {
		T[v].first=min(T[v].first,p);
		T[v].second=min(T[v].second,T[v].first);
		return;
	}
	int tm=(tl+tr)/2;
	updMn(tl,tm,tl,tm,2*v,T[v].first, 1);
	updMn(tm+1,tr,tm+1,tr,2*v+1,T[v].first, 1);
	updMx(tl,tm,tl,tm,2*v,T[v].second, 1);
	updMx(tm+1,tr,tm+1,tr,2*v+1,T[v].second, 1);
	T[v]={2e9,0};
	updMn(l,min(r,tm), tl, tm, 2*v, p);
	updMn(max(l,tm+1),r, tm+1, tr, 2*v+1, p);
}
void updMx(int l, int r, int tl, int tr, int v, int p, int d=0) {
	if(l>r)return;
	if(l==tl and r==tr) {
		T[v].second=max(T[v].second,p);
		T[v].first=max(T[v].first,T[v].second);
		return;
	}
	int tm=(tl+tr)/2;
	updMn(tl,tm,tl,tm,2*v,T[v].first, 1);
	updMn(tm+1,tr,tm+1,tr,2*v+1,T[v].first, 1);
	updMx(tl,tm,tl,tm,2*v,T[v].second, 1);
	updMx(tm+1,tr,tm+1,tr,2*v+1,T[v].second, 1);
	T[v]={2e9,0};
	updMx(l,min(r,tm), tl, tm, 2*v, p);
	updMx(max(l,tm+1),r, tm+1, tr, 2*v+1, p);
}
int get(int tl, int tr, int v, int p) {
	if(tl == tr and tl==p) {
		return min(T[v].first,T[v].second);
	}
	int tm=(tl+tr)/2;
	updMn(tl,tm,tl,tm,2*v,T[v].first, 1);
	updMn(tm+1,tr,tm+1,tr,2*v+1,T[v].first, 1);
	updMx(tl,tm,tl,tm,2*v,T[v].second, 1);
	updMx(tm+1,tr,tm+1,tr,2*v+1,T[v].second, 1);
	if(p<=tm) {
		return get(tl,tm,2*v,p);
	}
	return get(tm+1,tr,2*v+1,p);

}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i =0;i<4*N;i++)T[i]={2e9,0};
	for(int i = 0;i<k;i++) {
		if(op[i]==1) {
			updMx(left[i],right[i],0,n-1,1,height[i]);
		}
		else {
			updMn(left[i],right[i],0,n-1,1,height[i]);
		}
	}
	for(int i = 0;i<n;i++) {
		finalHeight[i]=get(0,n-1,1,i);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62800 KB Output is correct
2 Correct 34 ms 62924 KB Output is correct
3 Correct 38 ms 62960 KB Output is correct
4 Correct 39 ms 63048 KB Output is correct
5 Correct 41 ms 63052 KB Output is correct
6 Correct 39 ms 63104 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62864 KB Output is correct
2 Correct 150 ms 76548 KB Output is correct
3 Correct 252 ms 70004 KB Output is correct
4 Correct 695 ms 80968 KB Output is correct
5 Correct 473 ms 81980 KB Output is correct
6 Correct 458 ms 80372 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62856 KB Output is correct
2 Correct 34 ms 63044 KB Output is correct
3 Correct 31 ms 62960 KB Output is correct
4 Correct 38 ms 63156 KB Output is correct
5 Correct 37 ms 63164 KB Output is correct
6 Correct 37 ms 63164 KB Output is correct
7 Correct 31 ms 62856 KB Output is correct
8 Correct 161 ms 76564 KB Output is correct
9 Correct 252 ms 70136 KB Output is correct
10 Correct 729 ms 80876 KB Output is correct
11 Correct 467 ms 81936 KB Output is correct
12 Correct 465 ms 80360 KB Output is correct
13 Correct 28 ms 62804 KB Output is correct
14 Correct 150 ms 76472 KB Output is correct
15 Correct 69 ms 64020 KB Output is correct
16 Correct 687 ms 81200 KB Output is correct
17 Correct 494 ms 80552 KB Output is correct
18 Correct 456 ms 80584 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62800 KB Output is correct
2 Correct 29 ms 63056 KB Output is correct
3 Correct 31 ms 62928 KB Output is correct
4 Correct 37 ms 63040 KB Output is correct
5 Correct 36 ms 63060 KB Output is correct
6 Correct 35 ms 63052 KB Output is correct
7 Correct 31 ms 62896 KB Output is correct
8 Correct 162 ms 76516 KB Output is correct
9 Correct 258 ms 70008 KB Output is correct
10 Correct 702 ms 80920 KB Output is correct
11 Correct 454 ms 82084 KB Output is correct
12 Correct 445 ms 80424 KB Output is correct
13 Correct 27 ms 62796 KB Output is correct
14 Correct 156 ms 76548 KB Output is correct
15 Correct 66 ms 64092 KB Output is correct
16 Correct 668 ms 81156 KB Output is correct
17 Correct 462 ms 80564 KB Output is correct
18 Correct 456 ms 80588 KB Output is correct
19 Correct 1875 ms 99336 KB Output is correct
20 Correct 1878 ms 96696 KB Output is correct
21 Correct 1875 ms 99232 KB Output is correct
22 Correct 1831 ms 96800 KB Output is correct
23 Correct 1828 ms 96832 KB Output is correct
24 Correct 1833 ms 96848 KB Output is correct
25 Correct 1834 ms 96788 KB Output is correct
26 Correct 1842 ms 99396 KB Output is correct
27 Correct 1827 ms 99276 KB Output is correct
28 Correct 1821 ms 96716 KB Output is correct
29 Correct 1819 ms 96812 KB Output is correct
30 Correct 1834 ms 96912 KB Output is correct