oj.uz

Submission #554401

# Submission time Handle Problem Language Result Execution time Memory
554401 2022-04-28T10:43:53 Z Koosha_mv Wall (IOI14_wall) C++14
100 / 100
 777 ms 114380 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#include "wall.h"

const int N=2e6+99;

int n,m,q,mx0,mx1;
int ans[N],seg[2][N];
vector<pair<int,int>> A;
vector<pair<int,pair<int,int>>> vec[N];

void upd(int x,int val,int s,int id=1,int l=0,int r=m){
	if(r<=x || x<l) return ;
	if(l+1==r){
		seg[s][id]=val;
		return ;
	}
	int mid=(l+r)>>1;
	upd(x,val,s,id<<1,l,mid);
	upd(x,val,s,id<<1|1,mid,r);
	seg[s][id]=max(seg[s][id<<1],seg[s][id<<1|1]);
}
int get(int id=1,int l=0,int r=m){
	if(l+1==r) return A[l].F;
	int mid=(l+r)>>1;
	if(max(mx0,seg[0][id<<1])>=max(mx1,seg[1][id<<1|1])){
		maxm(mx1,seg[1][id<<1|1]);
		return get(id<<1,l,mid);
	}
	maxm(mx0,seg[0][id<<1]);
	return get(id<<1|1,mid,r);
}
void buildWall(int _n,int _k,int op[],int left[],int right[],int height[],int finalHeight[]){
	n=_n;
	q=_k;
	f(i,0,q) A.pb({height[i],i}),right[i]++,op[i]=2-op[i];
	A.pb({0,-1});
	sort(all(A));
	f(i,0,q){
		int x=lower_bound(all(A),mp(height[i],i))-A.begin();
		vec[left[i]].pb({op[i],{x,i+1}});
		vec[right[i]].pb({op[i],{x,0}});
	}
	m=A.size();
	f(i,0,n){
		for(auto p : vec[i]) upd(p.S.F,p.S.S,p.F);
		mx0=mx1=0;
		ans[i]=get();
	}
	f(i,0,n) finalHeight[i]=ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 28 ms 47740 KB Output is correct
3 Correct 24 ms 47444 KB Output is correct
4 Correct 30 ms 47844 KB Output is correct
5 Correct 28 ms 47876 KB Output is correct
6 Correct 32 ms 47772 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 442 ms 79192 KB Output is correct
3 Correct 258 ms 64116 KB Output is correct
4 Correct 776 ms 88092 KB Output is correct
5 Correct 460 ms 81716 KB Output is correct
6 Correct 450 ms 81016 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47164 KB Output is correct
2 Correct 28 ms 47736 KB Output is correct
3 Correct 26 ms 47436 KB Output is correct
4 Correct 32 ms 47868 KB Output is correct
5 Correct 33 ms 47956 KB Output is correct
6 Correct 28 ms 47828 KB Output is correct
7 Correct 23 ms 47188 KB Output is correct
8 Correct 427 ms 79116 KB Output is correct
9 Correct 263 ms 64156 KB Output is correct
10 Correct 751 ms 88076 KB Output is correct
11 Correct 462 ms 81588 KB Output is correct
12 Correct 466 ms 81120 KB Output is correct
13 Correct 25 ms 47180 KB Output is correct
14 Correct 461 ms 79072 KB Output is correct
15 Correct 57 ms 49992 KB Output is correct
16 Correct 756 ms 88480 KB Output is correct
17 Correct 480 ms 80884 KB Output is correct
18 Correct 455 ms 80296 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 27 ms 47828 KB Output is correct
3 Correct 24 ms 47436 KB Output is correct
4 Correct 29 ms 47828 KB Output is correct
5 Correct 29 ms 47800 KB Output is correct
6 Correct 29 ms 47828 KB Output is correct
7 Correct 24 ms 47308 KB Output is correct
8 Correct 430 ms 79116 KB Output is correct
9 Correct 272 ms 64188 KB Output is correct
10 Correct 775 ms 87988 KB Output is correct
11 Correct 459 ms 81704 KB Output is correct
12 Correct 449 ms 81072 KB Output is correct
13 Correct 23 ms 47268 KB Output is correct
14 Correct 468 ms 79088 KB Output is correct
15 Correct 56 ms 49992 KB Output is correct
16 Correct 777 ms 88352 KB Output is correct
17 Correct 449 ms 80924 KB Output is correct
18 Correct 451 ms 80288 KB Output is correct
19 Correct 760 ms 114284 KB Output is correct
20 Correct 749 ms 111840 KB Output is correct
21 Correct 755 ms 114380 KB Output is correct
22 Correct 753 ms 111836 KB Output is correct
23 Correct 751 ms 111796 KB Output is correct
24 Correct 749 ms 111676 KB Output is correct
25 Correct 763 ms 111708 KB Output is correct
26 Correct 757 ms 114312 KB Output is correct
27 Correct 761 ms 114364 KB Output is correct
28 Correct 757 ms 111736 KB Output is correct
29 Correct 759 ms 111668 KB Output is correct
30 Correct 755 ms 111768 KB Output is correct