Submission #930095

#	Time	Username	Problem	Language	Result	Execution time	Memory
930095		HuyQuang_re_Zero	Seats (IOI18_seats)	C++14	100 / 100	3031 ms	140112 KiB

seats

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "seats.h"
struct pt
{
    int mi3,mi1,slmi;
    friend pt operator + (pt a,pt b)
    {
        if(a.mi3<b.mi3) return a;
        if(b.mi3<a.mi3) return b;
        if(a.mi1<b.mi1) return a;
        if(b.mi1<a.mi1) return b;
        return { a.mi3,a.mi1,a.slmi+b.slmi };
    }
};
struct Interval_Tree
{
    pt st[4*maxn];
    int lz3[4*maxn],lz1[4*maxn];
    void change(int id,int k3,int k1)
    {
        st[id].mi3+=k3;
        st[id].mi1+=k1;
        lz3[id]+=k3;
        lz1[id]+=k1;
    }
    void down(int id)
    {
        change(id*2,lz3[id],lz1[id]);
        change(id*2+1,lz3[id],lz1[id]);
        lz3[id]=lz1[id]=0;
    }
    void build(int id,int l,int r)
    {
        if(l==r) { st[id]={ 0,0,1 }; return ; }
        int mid=(l+r)>>1;
        build(id*2,l,mid); build(id*2+1,mid+1,r);
        st[id]=st[id*2]+st[id*2+1];
    }
    void update(int id,int l,int r,int u,int v,int k3,int k1)
    {
        if(u>r || v<l) return ;
        if(u<=l && r<=v) { change(id,k3,k1); return ; }
        down(id);
        int mid=(l+r)>>1;
        update(id*2,l,mid,u,v,k3,k1); update(id*2+1,mid+1,r,u,v,k3,k1);
        st[id]=st[id*2]+st[id*2+1];
    }
} IT;

vector <int> a[maxn];
int n,m,x[maxn],y[maxn],i,j;
void Work(int x,int y,int k)
{
    if(a[x][y]==-1 || a[x][y+1]==-1 || a[x+1][y]==-1 || a[x+1][y+1]==-1) return ;
    vector <int> vec;
    vec.push_back(a[x][y]);
    vec.push_back(a[x][y+1]);
    vec.push_back(a[x+1][y]);
    vec.push_back(a[x+1][y+1]);
    sort(vec.begin(),vec.end());
    IT.update(1,1,n*m,vec[0],vec[1]-1,0,k);
    IT.update(1,1,n*m,vec[2],vec[3]-1,k,0);
}
void give_initial_chart(int _n,int _m,vector <int> _X,vector <int> _Y)
{
    n=_n; m=_m;
    for(i=0;i<n*m;i++) x[i+1]=_X[i]+1,y[i+1]=_Y[i]+1;
    for(i=0;i<=n+1;i++) a[i].resize(m+2);
    for(i=1;i<=n*m;i++) a[x[i]][y[i]]=i;
    for(i=0;i<=m+1;i++) a[0][i]=a[n+1][i]=n*m+1;
    for(i=1;i<=n;i++) a[i][0]=a[i][m+1]=n*m+1;

    IT.build(1,1,n*m);
    for(i=0;i<=n;i++)
        for(j=0;j<=m;j++) Work(i,j,1);
}


int swap_seats(int u,int v)
{
    u++; v++;
    Work(x[u]-1,y[u]-1,-1);
    Work(x[u]-1,y[u],-1);
    Work(x[u],y[u]-1,-1);
    Work(x[u],y[u],-1);
    a[x[u]][y[u]]=-1;
    Work(x[v]-1,y[v]-1,-1);
    Work(x[v]-1,y[v],-1);
    Work(x[v],y[v]-1,-1);
    Work(x[v],y[v],-1);
    a[x[v]][y[v]]=-1;

    swap(x[u],x[v]);
    swap(y[u],y[v]);
    a[x[u]][y[u]]=u;
    Work(x[u]-1,y[u]-1,1);
    Work(x[u]-1,y[u],1);
    Work(x[u],y[u]-1,1);
    Work(x[u],y[u],1);

    a[x[v]][y[v]]=v;
    Work(x[v]-1,y[v]-1,1);
    Work(x[v]-1,y[v],1);
    Work(x[v],y[v]-1,1);
    Work(x[v],y[v],1);

    return IT.st[1].slmi;
}

/*
int main()
{
    freopen("seats.inp","r",stdin);
    freopen("seats.out","w",stdout);
    int n,m,q,i,x,y,k;
    vector <int> X,Y;
    cin>>n>>m>>q;
    for(i=1;i<=n*m;i++) cin>>x>>y,X.push_back(x),Y.push_back(y);
    give_initial_chart(n,m,X,Y);
    for(i=1;i<=q;i++) cin>>x>>y,cout<<swap_seats(x,y)<<'\n';
}
*/

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