Submission #51634

#	Time	Username	Problem	Language	Result	Execution time	Memory
51634		Diuven	단층 (JOI16_ho_t5)	C++11	100 / 100	227 ms	9124 KiB

2016_ho_t5

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const int MX=200010, inf=2e9;

int n, q;

struct {
    int x, d, l;
} L[MX];

struct BIT {
    int n;
    ll tree[MX];
    void init(int sz){
        n=sz;
        for(int i=1; i<=n; i++) tree[i]=0;
    }
    void upt(int pos, ll d){
        for(; pos>0; pos-=pos&(-pos))
            tree[pos]+=d;
    }
    void upt(int l, int r, ll d){
        if(r<l) return;
        upt(r,d); upt(l-1,-d);
    }
    ll val(int x){
        ll res=0;
        for(; 0<x && x<=n; x+=x&(-x))
            res+=tree[x];
        return res;
    }
} UT, VT;

void process(int idx){
    if(L[idx].d==1){
        if(VT.val(1)<L[idx].x) return;
        int l=1, r;
        {
            int s=1, e=n;
            while(s<e){
                int m=(s+e+1)/2;
                if(VT.val(m)>=L[idx].x) s=m;
                else e=m-1;
            }
            r=s;
        }
        UT.upt(l,r,-L[idx].l);
    }
    else{
        if(UT.val(n)<L[idx].x) return;
        int l, r=n;
        {
            int s=1, e=n;
            while(s<e){
                int m=(s+e)/2;
                if(UT.val(m)>=L[idx].x) e=m;
                else s=m+1;
            }
            l=s;
        }
        VT.upt(l,r,-L[idx].l);
    }

}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    UT.init(n); VT.init(n);
    for(int i=1; i<=q; i++){
        int x, d, l;
        cin>>x>>d>>l;
        // v>=x, u+=l
        if(d==1) L[i]={-x,d,2*l};
        // u>=x, v+=l
        else L[i]={x+1,d,2*l};
    }
    for(int i=1; i<=n; i++){
        UT.upt(i,i,i);
        VT.upt(i,i,-i);
    }
    for(int i=q; i>=1; i--){
        process(i);
    }
    for(int i=1; i<=n; i++)
        cout<<-((UT.val(i)+VT.val(i))/2)<<'\n';
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 16 / 16
• Subtask 3: 66 / 66