제출 #991394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991394		hirayuu_oj	자리 배치 (IOI18_seats)	C++17	5 / 100	4049 ms	86508 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;
using pll=pair<ll,ll>;
constexpr ll LINF=(1LL<<62)-(1LL<<31);

#include "seats.h"

template<class T,auto op,auto e>
struct SegTree{
    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);
    }
};

pll mx(pll x,pll y){
    return {min(x.first,y.first),max(x.second,y.second)};
}
pll e(){
    return {LINF,-LINF};
}
SegTree<pll, mx, e> x(1000000);
SegTree<pll, mx, e> y(1000000);
vector<int> r,c;
int h,w;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h=H;
    w=W;
    r=R;
    c=C;
    rep(i,H*W){
        x.set(i,pll(R[i],R[i]));
    }
    rep(i,H*W){
        y.set(i,pll(C[i],C[i]));
    }
}
int get(int i){
    pll xs=x.prod(0,i+1);
    pll ys=y.prod(0,i+1);
    return (xs.second-xs.first+1)*(ys.second-ys.first+1);
}

int swap_seats(int a, int b) {
    if(a>b)swap(a,b);
    swap(r[a],r[b]);
    swap(c[a],c[b]);
    x.set(a,{r[a],r[a]});
    x.set(b,{r[b],r[b]});
    y.set(a,{c[a],c[a]});
    y.set(b,{c[b],c[b]});
    int ans=1;
    int now=1;
    int lst=0;
    while(now<h*w){
        int ok=h*w-1,ng=lst;
        while(ok-ng>1){
            int mid=(ok+ng)>>1;
            if(get(mid)>now){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        now=get(ok);
        lst=ok;
        if(now==get(now-1)){
            ans++;
        }
    }
    return ans;
}

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