Submission #210590

#	Time	Username	Problem	Language	Result	Execution time	Memory
210590		medk	Seats (IOI18_seats)	C++14	31 / 100	4100 ms	60280 KiB

seats

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

#define ll long long
#define pb push_back
#define x first
#define y second

using namespace std;

const int MAXN=1e6+2;
int H,W;
vector<int> X,Y;

int sgt[4*MAXN][4]; //X(min,max) Y(min,max)

void build(int p=1, int l=0, int r=H*W-1)
{
    if(l==r)
    {
        sgt[p][0]=X[l];
        sgt[p][1]=X[l];
        sgt[p][2]=Y[l];
        sgt[p][3]=Y[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sgt[p][0]=min(sgt[p*2][0], sgt[p*2+1][0]);
    sgt[p][2]=min(sgt[p*2][2], sgt[p*2+1][2]);
    sgt[p][1]=max(sgt[p*2][1], sgt[p*2+1][1]);
    sgt[p][3]=max(sgt[p*2][3], sgt[p*2+1][3]);
}

void update(int id, int p=1, int l=0, int r=H*W-1)
{
    if(l==r)
    {
        sgt[p][0]=X[l];
        sgt[p][1]=X[l];
        sgt[p][2]=Y[l];
        sgt[p][3]=Y[l];
        return;
    }
    int mid=(l+r)/2;
    if(id<=mid) update(id,p*2,l,mid);
    else update(id,p*2+1,mid+1,r);
    sgt[p][0]=min(sgt[p*2][0], sgt[p*2+1][0]);
    sgt[p][2]=min(sgt[p*2][2], sgt[p*2+1][2]);
    sgt[p][1]=max(sgt[p*2][1], sgt[p*2+1][1]);
    sgt[p][3]=max(sgt[p*2][3], sgt[p*2+1][3]);
}

pair<pair<int,int>,pair<int,int>> get(int a, int b, int p=1, int l=0, int r=H*W-1)
{
    if(l>=a && r<=b) return {{sgt[p][0],sgt[p][1]},{sgt[p][2],sgt[p][3]}};
    int mid=(l+r)>>1; // l mid a b
    int mnX=1e9, mxX=-1, mnY=1e9, mxY=-1;
    if(l<=b  && mid>=a)
    {
        auto pr=get(a,b,p*2,l,mid);
        mnX=min(mnX,pr.x.x);
        mxX=max(mxX,pr.x.y);
        mnY=min(mnY,pr.y.x);
        mxY=max(mxY,pr.y.y);
    }
    if(mid+1<=b  && r>=a)
    {
        auto pr=get(a,b,p*2+1,mid+1,r);
        mnX=min(mnX,pr.x.x);
        mxX=max(mxX,pr.x.y);
        mnY=min(mnY,pr.y.x);
        mxY=max(mxY,pr.y.y);
    }
    return {{mnX,mxX},{mnY,mxY}};
}

void give_initial_chart(int h,int w, vector<int> y, vector<int> x)
{
    H=h, W=w;
    X=x, Y=y;
    build();
}

int swap_seats(int a, int b)
{
    swap(X[a],X[b]);
    swap(Y[a],Y[b]);
    int ret=0;
    int prev[4]={(int)1e9,-1,(int)1e9,-1};
    if(H*W<=10000)
    {
        for(int i=0;i<H*W;i++)
        {
            prev[0]=min(X[i],prev[0]);
            prev[1]=max(X[i],prev[1]);
            prev[2]=min(Y[i],prev[2]);
            prev[3]=max(Y[i],prev[3]);
            if((prev[1]-prev[0]+1)*(prev[3]-prev[2]+1)==i+1) ret++;
        }
        return ret;
    }
    int ptr=0;
    int from=0;
    update(a), update(b);
    while(ptr<H*W)
    {
        auto gt=get(from,ptr);
        gt.x.x=min(gt.x.x,prev[0]);
        gt.y.x=min(gt.y.x,prev[2]);
        gt.x.y=max(gt.x.y,prev[1]);
        gt.y.y=max(gt.y.y,prev[3]);
        int where=(gt.x.y-gt.x.x+1)*(gt.y.y-gt.y.x+1)-1;
        from=ptr+1;
        if(where==ptr)
        {
            ret++;
            ptr+=min(gt.x.y-gt.x.x+1,gt.y.y-gt.y.x+1);
            prev[0]=gt.x.x;
            prev[1]=gt.x.y;
            prev[2]=gt.y.x;
            prev[3]=gt.y.y;
        }
        else
        {
            ptr=where;
            prev[0]=gt.x.x;
            prev[1]=gt.x.y;
            prev[2]=gt.y.x;
            prev[3]=gt.y.y;
        }
    }
    return ret;
}

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