Submission #991357

#	Time	Username	Problem	Language	Result	Execution time	Memory
991357		hirayuu_oj	Seats (IOI18_seats)	C++17	33 / 100	755 ms	93172 KiB

seats

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll LINF=(1LL<<62)-(1LL<<31);

#include "seats.h"

struct SegTree{
    using T=array<ll,3>;
    //{cum,min,cnt}
    T op(T x,T y){
        T ret;
        ret[0]=x[0]+y[0];
        ret[1]=min(x[0]+y[1],x[1]);
        ret[2]=0;
        if(ret[1]==x[1]){
            ret[2]+=x[2];
        }
        if(ret[1]==x[0]+y[1]){
            ret[2]+=y[2];
        }
        return ret;
    }
    T e(){
        return {0,1<<30,0};
    }
    vector<T> val;
    int size;
    SegTree(int sz){
        size=sz;
        val.resize(size*2,e());
    }
    void set(int pos,T v){
        pos+=size;
        val[pos]=v;
        while(pos>1){
            pos/=2;
            val[pos]=op(val[pos*2],val[pos*2+1]);
        }
    }
    T prod(int lf,int ri){
        lf+=size;
        ri+=size;
        T ret_lf=e();
        T ret_ri=e();
        while(lf<ri){
            if(lf&1){
                ret_lf=op(ret_lf,val[lf]);
                lf++;
            }
            if(ri&1){
                ri--;
                ret_ri=op(val[ri],ret_ri);
            }
            lf/=2;
            ri/=2;
        }
        return op(ret_lf,ret_ri);
    }
};

//c...pos now...seats
vector<int> c;
vector<int> now;
vector<int> cum;
int w;
SegTree seg(0);
void seg_set(int pos){
    seg.set(pos,array<ll,3>{cum[pos],cum[pos],1});
}
void add(int pos,int val){
    if(pos!=0){
        if(now[pos-1]<now[pos]){
            cum[now[pos-1]]+=val;
            cum[now[pos]]-=val;
            seg_set(now[pos-1]);
        }
    }
    if(pos!=w+1){
        if(now[pos+1]<now[pos]){
            cum[now[pos+1]]+=val;
            cum[now[pos]]-=val;
            seg_set(now[pos+1]);
        }
    }
    seg_set(now[pos]);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    c = C;
    w = W;
    rep(i,W){
        c[i]++;
    }
    c.emplace_back(0);
    c.emplace_back(W+1);
    now.resize(W+2);
    cum.resize(W+2,0);
    seg=SegTree(W+2);
    rep(i,W+2){
        seg.set(i,array<ll,3>{0,0,1});
    }
    rep(i,W+2){
        now[c[i]]=i;
    }
    rep(i,W+2){
        add(i,1);
    }
}

int swap_seats(int a, int b) {
    vector<int> fix={c[a],c[a]+1,c[a]-1,c[b],c[b]+1,c[b]-1};
    sort(all(fix));
    fix.erase(unique(all(fix)),fix.end());
    for(int i:fix){
        add(i,-1);
    }
    swap(c[a],c[b]);
    swap(now[c[a]],now[c[b]]);
    for(int i:fix){
        add(i,1);
    }
    return seg.prod(0,w)[2];
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 33 / 33
• Subtask 6: 0 / 30