Submission #1105784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105784		hihihihaw	Wall (IOI14_wall)	C++17	100 / 100	446 ms	103616 KiB

wall

#pragma GCC optimize("O3,unroll-loops")    
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define pii pair<int,int>
#define sz(v) (int)v.size()
#define fi first
#define se second
#define INF 1223372036854775807
#define MOD  998244353
#define cint(x) int x;cin>>x;
#define cinarr(a,n) int a[n];for (int i=0;i<n;i++) cin>>a[i];
#define coutarr(a) for (auto d:a)cout<<d<<" "; cout<<endl;
#define coutarrD(a) for (auto d:a) cout<<d.fi<<","<<d.se<<" "; cout<<endl;
#define BERKAY_TUP ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
#define ld long double
#define mid (start+end)/2
#define vvi vector<vector<int>>
int lazy[8000023][2];
int res[2000023];
void apply(int node,int a,int b){
    if (b<=lazy[node][0]){
        lazy[node][0]=b;
        lazy[node][1]=b;
    }
    else if (a>=lazy[node][1]){
        lazy[node][0]=a;
        lazy[node][1]=a;
    }
    else if (a>=lazy[node][0] && b<=lazy[node][1]){
        lazy[node][0]=a;
        lazy[node][1]=b;
    }
    else{
        lazy[node][0]=max(lazy[node][0],a);
        lazy[node][1]=min(lazy[node][1],b);
    }
}
void push(int node,int start,int end){
    int a=lazy[node][0],b=lazy[node][1];
    //cout<<"pushed "<<node<<" "<<start<<" "<<end<<" "<<a<<" "<<b<<endl;
    apply(node*2,a,b);
    apply(node*2+1,a,b);
    lazy[node][0]=0;
    lazy[node][1]=99999999;
}
void update(int node,int start,int end,int l,int r,int a,int b){
    //cout<<"-  "<<node<<" "<<start<<" "<<end<<endl;
    if (start>end ||start>r || end<l) return;
    if (start>=l && end<=r){
        //cout<<"updated "<<node<<endl;
        //cout<<"with "<<a<<" "<<b<<endl;
        //cout<<lazy[node][0]<<" "<<lazy[node][1]<<endl;
        apply(node,a,b);
        //cout<<lazy[node][0]<<" "<<lazy[node][1]<<endl;
        return;
    }
    push(node,start,end);
    update(node*2,start,mid,l,r,a,b);
    update(node*2+1,mid+1,end,l,r,a,b);
}
void pushAll(int node,int start,int end){
    if (start==end){
        res[start-1]=lazy[node][0];
        return;
    }
    push(node,start,end);
    pushAll(node*2,start,mid);
    pushAll(node*2+1,mid+1,end);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i=1;i<4*n+10;i++){
        lazy[i][0]=0;
        lazy[i][1]=99999999;
    }
    for (int i=0;i<k;i++){
        int a=0,b=999999999;
        if (op[i]==1) a=height[i];
        else b=height[i];
        update(1,1,n,left[i]+1,right[i]+1,a,b);
    }
    //cout<<"---"<<endl;
    pushAll(1,1,n);
    for (int i=0;i<n;i++) finalHeight[i]=res[i];
    return;
}

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