제출 #431817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431817		Bench0310	자리 배치 (IOI18_seats)	C++17	11 / 100	4048 ms	102572 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"

using namespace std;
typedef long long ll;

int n,h,w;
vector<array<int,2>> v;
vector<int> ar,br,ac,bc;
int res=0;
vector<array<int,4>> tree;

array<int,4> tmerge(array<int,4> l,array<int,4> r)
{
    array<int,4> tmp;
    auto &[a,b,c,d]=tmp;
    auto &[la,lb,lc,ld]=l;
    auto &[ra,rb,rc,rd]=r;
    a=min(la,ra);
    b=max(lb,rb);
    c=min(lc,rc);
    d=max(ld,rd);
    return tmp;
}

void update(int idx,int l,int r,int pos,array<int,4> val)
{
    if(l==r) tree[idx]=val;
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,val);
        else update(2*idx+1,m+1,r,pos,val);
        tree[idx]=tmerge(tree[2*idx],tree[2*idx+1]);
    }
}

array<int,4> query(int idx,int l,int r,int ql,int qr)
{
    if(ql>qr) return {n,-1,n,-1};
    if(l==ql&&r==qr) return tree[idx];
    int m=(l+r)/2;
    return tmerge(query(2*idx,l,m,ql,min(qr,m)),query(2*idx+1,m+1,r,max(ql,m+1),qr));
}

int ok(int i){return ((br[i]-ar[i]+1)*(bc[i]-ac[i]+1)==i+1);}

void give_initial_chart(int nh,int nw,vector<int> r,vector<int> c)
{
    h=nh;
    w=nw;
    n=h*w;
    tree.assign(4*(n+5),{0,0,0,0});
    v.assign(n,{0,0});
    for(int i=0;i<n;i++) v[i]={r[i],c[i]};
    ar.assign(n,v[0][0]);
    br.assign(n,v[0][0]);
    ac.assign(n,v[0][1]);
    bc.assign(n,v[0][1]);
    res=ok(0);
    for(int i=1;i<n;i++)
    {
        ar[i]=min(ar[i-1],v[i][0]);
        br[i]=max(br[i-1],v[i][0]);
        ac[i]=min(ac[i-1],v[i][1]);
        bc[i]=max(bc[i-1],v[i][1]);
        res+=ok(i);
    }
    for(int i=0;i<n;i++) update(1,0,n-1,i,{v[i][0],v[i][0],v[i][1],v[i][1]});
}

int swap_seats(int a,int b)
{
    if(a>b) swap(a,b);
    swap(v[a],v[b]);
    for(int i:{a,b}) update(1,0,n-1,i,{v[i][0],v[i][0],v[i][1],v[i][1]});
    if(h>1000||w>1000)
    {
        for(int i=a;i<=b;i++)
        {
            res-=ok(i);
            ar[i]=min((i>0?ar[i-1]:n),v[i][0]);
            br[i]=max((i>0?br[i-1]:0),v[i][0]);
            ac[i]=min((i>0?ac[i-1]:n),v[i][1]);
            bc[i]=max((i>0?bc[i-1]:0),v[i][1]);
            res+=ok(i);
        }
        return res;
    }
    else
    {
        int r=0;
        int now=0;
        int cnt=0;
//        cout << "in" << endl;
        while(now<n)
        {
//            cout << now << " ";
            auto [c,d,e,f]=query(1,0,n-1,0,now);
//            cout << "[" << c << "," << d << "," << e << "," << f << "] ";
//            cout.flush();
            if((d-c+1)*(f-e+1)==now+1) r++;
            now=max(now+1,(d-c+1)*(f-e+1)-1);
            cnt++;
        }
        assert(cnt<=2*(w+h));
//        cout << endl;
        return r;
    }
}

//int main()
//{
//    
//    return 0;
//}

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