제출 #1276896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276896		quanduongxuan12	벽 (IOI14_wall)	C++20	61 / 100	886 ms	276784 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define name "wall"
#define MAXN 2000006
#define pb push_back
#define pf push_front
#define ll long long
#define ii pair<int, int>
#define fs first
#define sc second
#define ill pair<int, ll>
#define lli pair<ll, int>
#define llll pair<ll, ll>
#define all(v) v.begin(),v.end()
#define uni(v) v.erase(unique(all(v)),v.end())
#define bit(n,i) (((n)>>(i))&1)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define MASK(i) (1LL<<(i))
const int INF=1e9;
const int MOD=1e9+7;
void add(int &u, int v){
    u+=v;
    if (u>=MOD) u-=MOD;
}
void sub(int &u, int v){
    u-=v;
    if (u<0) u+=MOD;
}
bool minimize(int &u, int v){
    if (u>v){
        u=v;
        return 1;
    }
    return 0;
}
bool maximize(int &u, int v){
    if (u<v){
        u=v;
        return 1;
    }
    return 0;
}
long long Rand(long long l, long long r){
    ll tmp=0;
    FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand()));
    return l+tmp%(r-l+1);
}
struct Node{
    ll sum;
    int Max1,Max2;
    int Maxc;
    int Min1,Min2;
    int Minc;
    Node(){
        sum=0;
        Max1=Max2=Maxc=Min1=Min2=Minc=0;
    }
    bool ok(){
        return Maxc>0;
    }
}st[4*MAXN];
Node unite(Node &A, Node &B){
    if (!A.ok()) return B;
    if (!B.ok()) return A;
    Node kq;
    kq.sum=A.sum+B.sum;
    if (A.Max1==B.Max1){
        kq.Max1=A.Max1;
        kq.Maxc=A.Maxc+B.Maxc;
        kq.Max2=max(A.Max2,B.Max2);
    }
    else if (A.Max1>B.Max1){
        kq.Max1=A.Max1;
        kq.Max2=max(A.Max2,B.Max1);
        kq.Maxc=A.Maxc;
    }
    else{
        kq.Max1=B.Max1;
        kq.Max2=max(A.Max1,B.Max2);
        kq.Maxc=B.Maxc;
    }
    if (A.Min1==B.Min1){
        kq.Min1=A.Min1;
        kq.Minc=A.Minc+B.Minc;
        kq.Min2=min(A.Min2,B.Min2);
    }
    else if (A.Min1<B.Min1){
        kq.Min1=A.Min1;
        kq.Min2=min(A.Min2,B.Min1);
        kq.Minc=A.Minc;
    }
    else{
        kq.Min1=B.Min1;
        kq.Min2=max(A.Min1,B.Min2);
        kq.Minc=B.Minc;
    }
    return kq;
}
void build(int id, int l, int r){
    if (l==r){
        st[id].sum=0;
        st[id].Maxc=st[id].Minc=1;
        st[id].Max1=st[id].Min1=0;
        st[id].Max2=-INF;
        st[id].Min2=INF;
        return;
    }
    int mid=(l+r)/2;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    st[id]=unite(st[id<<1],st[id<<1|1]);
}
void push_min(int id, int l, int r, int val){
    if (st[id].Max1<=val) return;
    st[id].sum-=1LL*st[id].Max1*st[id].Maxc;
    st[id].Max1=val;
    st[id].sum+=1LL*st[id].Max1*st[id].Maxc;
    if (l==r){
        st[id].Min1=val;
    }
    else{
        if (val<=st[id].Min1) st[id].Min1=val;
        else if (val<st[id].Min2) st[id].Min2=val;
    }
}
void push_max(int id, int l, int r, int val){
    if (st[id].Min1>=val) return;
    st[id].sum-=1LL*st[id].Min1*st[id].Minc;
    st[id].Min1=val;
    st[id].sum+=1LL*st[id].Min1*st[id].Minc;
    if (l==r){
        st[id].Max1=val;
    }
    else{
        if (val>=st[id].Max1) st[id].Max1=val;
        else if (val>st[id].Max2) st[id].Max2=val;
    }
}
void push_down(int id, int l, int r){
    if (l==r) return;
    int mid=(l+r)/2;
    push_min(id<<1,l,mid,st[id].Max1);
    push_min(id<<1|1,mid+1,r,st[id].Max1);
    push_max(id<<1,l,mid,st[id].Min1);
    push_max(id<<1|1,mid+1,r,st[id].Min1);
}
void update_min(int id, int l, int r, int u, int v, int val){
    if (l>v||r<u||st[id].Max1<=val) return;
    if (l>=u&&r<=v&&val>st[id].Max2){
        push_min(id,l,r,val);
        push_down(id,l,r);
        return;
    }
    push_down(id,l,r);
    int mid=(l+r)/2;
    update_min(id<<1,l,mid,u,v,val);
    update_min(id<<1|1,mid+1,r,u,v,val);
    st[id]=unite(st[id<<1],st[id<<1|1]);
}
void update_max(int id, int l, int r, int u, int v, int val){
    if (l>v||r<u||st[id].Min1>=val) return;
    if (l>=u&&r<=v&&val<st[id].Min2){
        push_max(id,l,r,val);
        push_down(id,l,r);
        return;
    }
    push_down(id,l,r);
    int mid=(l+r)/2;
    update_max(id<<1,l,mid,u,v,val);
    update_max(id<<1|1,mid+1,r,u,v,val);
    st[id]=unite(st[id<<1],st[id<<1|1]);
}
void get(int id, int l, int r, int res[]){
    if (l==r){
        res[l-1]=st[id].sum;
        return;
    }
    push_down(id,l,r);
    int mid=(l+r)/2;
    get(id<<1,l,mid,res);
    get(id<<1|1,mid+1,r,res);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int finalHeight[]){
    FORD(i,q,1){
        op[i]=op[i-1];
        l[i]=l[i-1]+1;
        r[i]=r[i-1]+1;
        h[i]=h[i-1];
    }
    build(1,1,n);
    FOR(i,1,q){
        int type=op[i],u=l[i],v=r[i],val=h[i];
        if (type==1) update_max(1,1,n,u,v,val);
        else update_min(1,1,n,u,v,val);
    }
    get(1,1,n,finalHeight);
}

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