oj.uz

Submission #430811

# Submission time Handle Problem Language Result Execution time Memory
430811 2021-06-17T05:59:39 Z CSQ31 Wall (IOI14_wall) C++17
100 / 100
 1477 ms 167212 KB 
#include "wall.h"
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e6+2;
vector<ll>mn(4*MAXN,INF),mx(4*MAXN,-INF);
vector<ll>ans(MAXN);
//each operation can be reduced to one max and min operation,call it x and y where y <=x (min first then max
//induction : 
//case 1: max opt with height h
//if(x<= h <= y) x=h
//if(h < x) do nothing
//if(y < h)x=y=h
//case 2 : min opt with height h
//if(x <= h <= y)y=h;
//if(y<h)do nothing
//if(x<h) x=y=h;
void apply(int a,int b){ //apply node a to node b
	mn[b] = min(mn[b],mn[a]);
	mx[b] = min(mx[b],mn[a]);
	mn[b] = max(mn[b],mx[a]);
	mx[b] = max(mx[b],mx[a]);	
}

void pushdown(int v){
	apply(v,2*v);
	apply(v,2*v+1);
	mn[v] = INF;
	mx[v] = -INF;
	
}
void upd(int v,int l,int r,int tl,int tr,ll v0,ll v1){
	if(l>r)return;
	if(tl!=tr)pushdown(v);
	if(l==tl && r==tr){
	    mn[v] = min(mn[v],v0);
	    mx[v] = min(mx[v],v0);
	    mn[v] = max(mn[v],v1);
	    mx[v] = max(mx[v],v1);
		return;
	}
	int tm = (tl+tr)/2;
	upd(2*v,l,min(r,tm),tl,tm,v0,v1);
	upd(2*v+1,max(tm+1,l),r,tm+1,tr,v0,v1);
}
void query(int v,int l,int r){
	if(l==r){
		ll res = 0;
		res = min(res,mn[v]);
		res = max(res,mx[v]);
		ans[l-1] = res;
		return;
	}
	int tm = (l+r)/2;
	pushdown(v);
	query(2*v,l,tm);
	query(2*v+1,tm+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<k;i++){
		ll v0 = INF;
		ll v1 = -INF;
		if(op[i] == 1)v1 = height[i];
		else v0 = height[i];
		
		upd(1,left[i]+1,right[i]+1,1,n,v0,v1);
		//cout<<"CUR:"<<i<<'\n';
		//print(1,1,n);
	}
	query(1,1,n);
	for(int i=0;i<n;i++)finalHeight[i] = ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 141088 KB Output is correct
2 Correct 67 ms 141204 KB Output is correct
3 Correct 70 ms 141132 KB Output is correct
4 Correct 78 ms 141252 KB Output is correct
5 Correct 76 ms 141308 KB Output is correct
6 Correct 78 ms 141272 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 141124 KB Output is correct
2 Correct 272 ms 149036 KB Output is correct
3 Correct 376 ms 144624 KB Output is correct
4 Correct 1074 ms 149692 KB Output is correct
5 Correct 527 ms 150060 KB Output is correct
6 Correct 525 ms 150072 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 141196 KB Output is correct
2 Correct 67 ms 141256 KB Output is correct
3 Correct 76 ms 141192 KB Output is correct
4 Correct 76 ms 141296 KB Output is correct
5 Correct 73 ms 141252 KB Output is correct
6 Correct 73 ms 141328 KB Output is correct
7 Correct 75 ms 141172 KB Output is correct
8 Correct 222 ms 149068 KB Output is correct
9 Correct 366 ms 144540 KB Output is correct
10 Correct 1075 ms 149560 KB Output is correct
11 Correct 527 ms 150036 KB Output is correct
12 Correct 517 ms 150156 KB Output is correct
13 Correct 76 ms 141128 KB Output is correct
14 Correct 223 ms 149004 KB Output is correct
15 Correct 130 ms 141764 KB Output is correct
16 Correct 1080 ms 149916 KB Output is correct
17 Correct 527 ms 149800 KB Output is correct
18 Correct 523 ms 149800 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 141124 KB Output is correct
2 Correct 68 ms 141224 KB Output is correct
3 Correct 70 ms 141292 KB Output is correct
4 Correct 77 ms 141328 KB Output is correct
5 Correct 75 ms 141348 KB Output is correct
6 Correct 73 ms 141356 KB Output is correct
7 Correct 66 ms 141088 KB Output is correct
8 Correct 219 ms 148964 KB Output is correct
9 Correct 376 ms 144452 KB Output is correct
10 Correct 1028 ms 149544 KB Output is correct
11 Correct 542 ms 150056 KB Output is correct
12 Correct 538 ms 150128 KB Output is correct
13 Correct 68 ms 141160 KB Output is correct
14 Correct 219 ms 149000 KB Output is correct
15 Correct 117 ms 141768 KB Output is correct
16 Correct 1127 ms 149800 KB Output is correct
17 Correct 522 ms 149956 KB Output is correct
18 Correct 523 ms 149800 KB Output is correct
19 Correct 1477 ms 167088 KB Output is correct
20 Correct 1415 ms 164636 KB Output is correct
21 Correct 1413 ms 167092 KB Output is correct
22 Correct 1452 ms 164732 KB Output is correct
23 Correct 1410 ms 164624 KB Output is correct
24 Correct 1464 ms 164556 KB Output is correct
25 Correct 1394 ms 164592 KB Output is correct
26 Correct 1421 ms 167212 KB Output is correct
27 Correct 1463 ms 167080 KB Output is correct
28 Correct 1425 ms 164556 KB Output is correct
29 Correct 1409 ms 164652 KB Output is correct
30 Correct 1411 ms 164544 KB Output is correct