Submission #338565

#	Time	Username	Problem	Language	Result	Execution time	Memory
338565		Sho10	Wall (IOI14_wall)	C++14	0 / 100	230 ms	8172 KiB

wall

#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#include "wall.h"
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
pair<int,int>tree[8000010];
void build(int node,int l,int r){
if(l==r){
    tree[node]=mp(-1,-1);
    return;
}
int mid=(l+r)/2;
build(2*node,l,mid);
build(2*node,mid+1,r);
}
void add(pair<int,int> &s,pair<int,int> &j){
if(s==mp(-1,-1)){
    return;
}
if(j==mp(-1,-1)){
    j=mp(s.f,s.s);
    s=mp(-1,-1);
    return;
}
int a,b,c,d;
a=s.f;
b=s.s;
c=j.f;
d=j.s;
if(b<c){
    j=mp(max(a,b),min(b,d));
}else {
j=mp(max(a,c),min(c,d));
}
s=mp(-1,-1);
return;
}
void update(int node,int l,int r,int st,int dr,int type,int h){
if(st>dr){
    return;
}
if(l==st&&r==dr){
        pair<int,int>p;
p.f=0;
p.s=0;
    if(type==1){
      p.f=h;
      p.s=INF;
    }else {
    p.s=h;
    }
    add(p,tree[node]);
    return;
}
pair<int,int>p=tree[node];
add(tree[node],tree[node*2]);
add(p,tree[node*2+1]);
int mid=(l+r)/2;
update(2*node,l,mid,st,min(dr,mid),type,h);
update(2*node+1,mid+1,r,max(st,mid+1),dr,type,h);
return;
}
int query(int node,int l,int r,int pos){
int mid=(l+r)/2;
if(l==r){
    return tree[node].f;
}
pair<int,int>p=tree[node];
add(tree[node],tree[node*2]);
add(p,tree[node*2+1]);
if(pos<=mid){
return query(2*node,l,mid,pos);
}else return query(2*node+1,mid+1,r,pos);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
build(1,1,n);
for(int i=0;i<k;i++)
{
    update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
}
for(int i=0;i<n;i++)
{
    finalHeight[i]=query(1,1,n,i+1);
}
return;
}
/*
int32_t main(){
CODE_START;
*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39