Submission #210559

#	Time	Username	Problem	Language	Result	Execution time	Memory
210559		medk	Seats (IOI18_seats)	C++14	5 / 100	4100 ms	86520 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;

int H,W;
vector<int> X,Y;

vector<pair<pair<int,int>,pair<int,int>>> sgt; //X(min,max) Y(min,max)

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

void update(int id, int p=1, int l=0, int r=H*W-1)
{
    if(l==r)
    {
        sgt[p]={{X[l],X[l]},{Y[l],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].x.x=min(sgt[p*2].x.x, sgt[p*2+1].x.x);
    sgt[p].y.x=min(sgt[p*2].y.x, sgt[p*2+1].y.x);
    sgt[p].x.y=max(sgt[p*2].x.y, sgt[p*2+1].x.y);
    sgt[p].y.y=max(sgt[p*2].y.y, sgt[p*2+1].y.y);
}

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==r) return sgt[p];
    int mid=(l+r)/2; // 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;
    sgt.resize(4*H*W);
    build();
}

int swap_seats(int a, int b)
{
    swap(X[a],X[b]);
    swap(Y[a],Y[b]);
    update(a), update(b);
    int ret=0;
    int ptr=0;
    while(ptr<H*W)
    {
        auto gt=get(0,ptr);
        int where=(gt.x.y-gt.x.x+1)*(gt.y.y-gt.y.x+1)-1;
        if(where==ptr)
        {
            ret++;
            ptr+=min(gt.x.y-gt.x.x+1,gt.y.y-gt.y.x+1);
        }
        else ptr=where;
    }
    return ret;
}

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