oj.uz

Submission #377881

# Submission time Handle Problem Language Result Execution time Memory
377881 2021-03-15T11:54:31 Z YJU Wall (IOI14_wall) C++14
100 / 100
 1147 ms 171628 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e6+5;
const ll MOD=1e9+7;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

struct node{
	ll l,r;
}seg[4*N];

node operator +(node A,node B){
	if(A.l>=B.r){
		return node{B.r,B.r};
	}else if(A.r<=B.l){
		return node{B.l,B.l};
	}else{
		assert(max(A.l,B.l)<=min(A.r,B.r));
		return node{max(A.l,B.l),min(A.r,B.r)};
	}
}

void ins(ll id,ll l,ll r,ll to,node del){
	if(l==r-1){seg[id]=del;return ;}
	ll mid=(l+r)>>1;
	if(to<mid){
		ins(id*2,l,mid,to,del);
	}else{
        ins(id*2+1,mid,r,to,del);
	}
	seg[id]=seg[id*2]+seg[id*2+1];
}

vector<ll> app[N],rem[N];

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	REP(i,k){
        ins(1,0,k,i,node{0,INF});
        app[left[i]].pb(i);
        rem[right[i]].pb(i);
	}
	REP(i,n){
		for(ll j:app[i]){
			node tmp;
			if(op[j]==1)tmp=node{height[j],INF};
			else tmp=node{0,height[j]};
            ins(1,0,k,j,tmp);
		}
		finalHeight[i]=seg[1].l;
		for(ll j:rem[i]){
            ins(1,0,k,j,node{0,INF});
		}
	}
	//REP(i,n)cout<<finalHeight[i]<<" \n"[i==n-1];
}
/*
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    int oper[]={1,2,2,1,1,2};
    int l[]   ={1,4,3,0,2,6};
    int r[]   ={8,9,6,5,2,7};
    int h[]   ={4,1,5,3,5,0};
	int ans[10];
	buildWall(10,6,oper,l,r,h,ans);
	REP(i,10)cout<<ans[i]<<" \n"[i==9];
	return 0;
}
//*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94188 KB Output is correct
2 Correct 67 ms 94828 KB Output is correct
3 Correct 69 ms 94444 KB Output is correct
4 Correct 68 ms 95084 KB Output is correct
5 Correct 67 ms 94976 KB Output is correct
6 Correct 67 ms 94956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 94284 KB Output is correct
2 Correct 520 ms 132548 KB Output is correct
3 Correct 373 ms 115544 KB Output is correct
4 Correct 1087 ms 143832 KB Output is correct
5 Correct 595 ms 142572 KB Output is correct
6 Correct 578 ms 140652 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94316 KB Output is correct
2 Correct 65 ms 94828 KB Output is correct
3 Correct 71 ms 94444 KB Output is correct
4 Correct 70 ms 95084 KB Output is correct
5 Correct 67 ms 94956 KB Output is correct
6 Correct 66 ms 94956 KB Output is correct
7 Correct 63 ms 94316 KB Output is correct
8 Correct 516 ms 132644 KB Output is correct
9 Correct 403 ms 115640 KB Output is correct
10 Correct 1043 ms 143796 KB Output is correct
11 Correct 653 ms 142704 KB Output is correct
12 Correct 584 ms 140652 KB Output is correct
13 Correct 63 ms 94464 KB Output is correct
14 Correct 528 ms 132420 KB Output is correct
15 Correct 110 ms 97516 KB Output is correct
16 Correct 1111 ms 143980 KB Output is correct
17 Correct 658 ms 140676 KB Output is correct
18 Correct 606 ms 140132 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94188 KB Output is correct
2 Correct 66 ms 94828 KB Output is correct
3 Correct 66 ms 94444 KB Output is correct
4 Correct 80 ms 95084 KB Output is correct
5 Correct 68 ms 94956 KB Output is correct
6 Correct 68 ms 94956 KB Output is correct
7 Correct 71 ms 94316 KB Output is correct
8 Correct 533 ms 132572 KB Output is correct
9 Correct 390 ms 115576 KB Output is correct
10 Correct 1075 ms 143696 KB Output is correct
11 Correct 575 ms 142572 KB Output is correct
12 Correct 625 ms 140504 KB Output is correct
13 Correct 63 ms 94316 KB Output is correct
14 Correct 544 ms 132548 KB Output is correct
15 Correct 107 ms 97516 KB Output is correct
16 Correct 1147 ms 143832 KB Output is correct
17 Correct 612 ms 140616 KB Output is correct
18 Correct 609 ms 140268 KB Output is correct
19 Correct 868 ms 171628 KB Output is correct
20 Correct 859 ms 168940 KB Output is correct
21 Correct 867 ms 171496 KB Output is correct
22 Correct 866 ms 169068 KB Output is correct
23 Correct 876 ms 168812 KB Output is correct
24 Correct 860 ms 169004 KB Output is correct
25 Correct 903 ms 168940 KB Output is correct
26 Correct 865 ms 171552 KB Output is correct
27 Correct 866 ms 171500 KB Output is correct
28 Correct 861 ms 168860 KB Output is correct
29 Correct 855 ms 169196 KB Output is correct
30 Correct 859 ms 168940 KB Output is correct