oj.uz

Submission #560609

# Submission time Handle Problem Language Result Execution time Memory
560609 2022-05-11T17:43:55 Z CSQ31 Wall (IOI14_wall) C++17
100 / 100
 1190 ms 232472 KB 
#include "wall.h"
#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 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 INF = 2e9;
struct node{
	int mx1 = 0,mx2 = -INF,mxc = 1;
	int mn1 = 0,mn2 = INF,mnc = 1;
	node(){}	
};
node merge(node a,node b){
	node c;
	if(a.mx1 == b.mx1){
		c.mx1 = a.mx1;
		c.mxc = a.mxc + b.mxc;
		c.mx2 = max(a.mx2,b.mx2);
	}else{
		if(a.mx1 < b.mx1)swap(a,b);
		c.mx1 = a.mx1;
		c.mxc = a.mxc;
		c.mx2 = max(a.mx2,b.mx1);
	}
	if(a.mn1 == b.mn1){
		c.mn1 = a.mn1;
		c.mnc = a.mnc + b.mnc;
		c.mn2 =  min(a.mn2,b.mn2);
	}else{
		if(a.mn1 > b.mn1)swap(a,b);
		c.mn1 = a.mn1;
		c.mnc = a.mnc;
		c.mn2 = min(a.mn2,b.mn1);
	}
	return c;
}
node t[8000000];
int ans[2000001];
void mxtag(int v,int x){
	if(x >= t[v].mx1)return;
	if(t[v].mx1 == t[v].mn1)t[v].mn1 = x;
	else if(t[v].mn2 == t[v].mx1)t[v].mn2 = x;
	t[v].mx1 = x;
}
void mntag(int v,int x){
	if(x <= t[v].mn1)return;
	if(t[v].mx1 == t[v].mn1)t[v].mx1 = x;
	else if(t[v].mx2 == t[v].mn1)t[v].mx2 = x; //mn,mx only two values
	t[v].mn1 = x;
}
void pushdown(int v){
	mxtag(2*v,t[v].mx1);
	mxtag(2*v+1,t[v].mx1);
	mntag(2*v,t[v].mn1);
	mntag(2*v+1,t[v].mn1);
	
}
void chmin(int v,int l,int r,int tl,int tr,int x){
	if(l > tr || r < tl || x >= t[v].mx1)return;
	if(l<=tl && tr<=r && x > t[v].mx2){
		mxtag(v,x);
		return;
	}
	int tm = (tl+tr)/2;
	pushdown(v);
	chmin(2*v,l,min(tm,r),tl,tm,x);
	chmin(2*v+1,max(tm+1,l),r,tm+1,tr,x);
	t[v] = merge(t[2*v],t[2*v+1]);
}
void chmax(int v,int l,int r,int tl,int tr,int x){
	if(l > tr || r < tl || x <= t[v].mn1)return;
	if(l<=tl && tr<=r && x < t[v].mn2){
		//cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<'\n';
		mntag(v,x);
		return;
	}
	int tm = (tl+tr)/2;
	pushdown(v);
	chmax(2*v,l,min(tm,r),tl,tm,x);
	chmax(2*v+1,max(tm+1,l),r,tm+1,tr,x);
	t[v] = merge(t[2*v],t[2*v+1]);
}
void query(int v,int l,int r){
	if(l==r){
		ans[l] = t[v].mx1;
		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++){
		if(op[i] == 1)chmax(1,left[i],right[i],0,n-1,height[i]);
		else chmin(1,left[i],right[i],0,n-1,height[i]);
	}
	query(1,0,n-1);
	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 104 ms 188048 KB Output is correct
2 Correct 106 ms 188204 KB Output is correct
3 Correct 116 ms 188216 KB Output is correct
4 Correct 116 ms 188392 KB Output is correct
5 Correct 111 ms 188364 KB Output is correct
6 Correct 104 ms 188408 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 188128 KB Output is correct
2 Correct 271 ms 201780 KB Output is correct
3 Correct 176 ms 195316 KB Output is correct
4 Correct 273 ms 206600 KB Output is correct
5 Correct 307 ms 207564 KB Output is correct
6 Correct 354 ms 206004 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 188128 KB Output is correct
2 Correct 104 ms 188184 KB Output is correct
3 Correct 97 ms 188116 KB Output is correct
4 Correct 113 ms 188356 KB Output is correct
5 Correct 98 ms 188356 KB Output is correct
6 Correct 105 ms 188404 KB Output is correct
7 Correct 98 ms 188128 KB Output is correct
8 Correct 232 ms 201748 KB Output is correct
9 Correct 170 ms 195368 KB Output is correct
10 Correct 276 ms 206508 KB Output is correct
11 Correct 289 ms 207660 KB Output is correct
12 Correct 368 ms 206076 KB Output is correct
13 Correct 93 ms 188108 KB Output is correct
14 Correct 226 ms 201740 KB Output is correct
15 Correct 143 ms 189364 KB Output is correct
16 Correct 916 ms 206764 KB Output is correct
17 Correct 547 ms 206188 KB Output is correct
18 Correct 549 ms 206316 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 188152 KB Output is correct
2 Correct 105 ms 188228 KB Output is correct
3 Correct 89 ms 188220 KB Output is correct
4 Correct 98 ms 188352 KB Output is correct
5 Correct 94 ms 188368 KB Output is correct
6 Correct 113 ms 188364 KB Output is correct
7 Correct 94 ms 188164 KB Output is correct
8 Correct 243 ms 201720 KB Output is correct
9 Correct 199 ms 195404 KB Output is correct
10 Correct 270 ms 206512 KB Output is correct
11 Correct 311 ms 207620 KB Output is correct
12 Correct 366 ms 206096 KB Output is correct
13 Correct 89 ms 188108 KB Output is correct
14 Correct 251 ms 201704 KB Output is correct
15 Correct 160 ms 189368 KB Output is correct
16 Correct 893 ms 206768 KB Output is correct
17 Correct 583 ms 206300 KB Output is correct
18 Correct 577 ms 206192 KB Output is correct
19 Correct 1190 ms 232300 KB Output is correct
20 Correct 1160 ms 229868 KB Output is correct
21 Correct 1121 ms 232472 KB Output is correct
22 Correct 1112 ms 229824 KB Output is correct
23 Correct 1158 ms 229884 KB Output is correct
24 Correct 1128 ms 229924 KB Output is correct
25 Correct 1145 ms 229964 KB Output is correct
26 Correct 1108 ms 232308 KB Output is correct
27 Correct 1117 ms 232384 KB Output is correct
28 Correct 1147 ms 229872 KB Output is correct
29 Correct 1120 ms 229860 KB Output is correct
30 Correct 1139 ms 229836 KB Output is correct