Submission #1095239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095239		onlk97	Seats (IOI18_seats)	C++14	100 / 100	2210 ms	228120 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

const int inf=1e9;
int n,m;
vector <vector <int> > grid;
vector <vector <array <int,4> > > v;
vector <pair <int,int> > pos;
int mn[12000100],cntmn[12000100],laz[12000100];
void pushup(int id){
    mn[id]=min(mn[2*id],mn[2*id+1]);
    cntmn[id]=0;
    if (mn[2*id]==mn[id]) cntmn[id]+=cntmn[2*id];
    if (mn[2*id+1]==mn[id]) cntmn[id]+=cntmn[2*id+1];
}
void pushdown(int id){
    mn[2*id]+=laz[id];
    mn[2*id+1]+=laz[id];
    laz[2*id]+=laz[id];
    laz[2*id+1]+=laz[id];
    laz[id]=0;
}
void build(int id,int tl,int tr){
    if (tl==tr){
        mn[id]=0; cntmn[id]=1; laz[id]=0;
        return;
    }
    int tm=(tl+tr)/2;
    build(2*id,tl,tm);
    build(2*id+1,tm+1,tr);
    pushup(id);
}
void update(int id,int tl,int tr,int l,int r,int val){
    if (l>r) return;
    if (l<=tl&&tr<=r){
        mn[id]+=val; laz[id]+=val;
        return;
    }
    pushdown(id);
    int tm=(tl+tr)/2;
    update(2*id,tl,tm,l,min(r,tm),val);
    update(2*id+1,tm+1,tr,max(l,tm+1),r,val);
    pushup(id);
}
void add(int l,int r,int val){
    update(1,1,(n+1)*(m+1),l,r,val);
}
void give_initial_chart(int H,int W,vector <int> R,vector <int> C){
    n=H; m=W; grid.clear(); v.clear();
    vector <int> tp(m+2,inf);
    for (int i=0; i<=n+1; i++) grid.push_back(tp);
    pos.push_back({0,0});
    for (int i=0; i<H*W; i++){
        grid[R[i]+1][C[i]+1]=i+1;
        pos.push_back({R[i]+1,C[i]+1});
    }
    vector <array <int,4> > tt(m+2,{inf,inf,inf,inf});
    for (int i=0; i<=n+1; i++) v.push_back(tt);
    for (int i=1; i<=n+1; i++){
        for (int j=1; j<=m+1; j++){
            int cnt=0;
            for (int d=-1; d<=0; d++){
                for (int e=-1; e<=0; e++){
                    v[i][j][cnt++]=grid[i+d][j+e];
                }
            }
            sort(v[i][j].begin(),v[i][j].end());
        }
    }
    build(1,1,(n+1)*(m+1));
    for (int i=1; i<=n+1; i++){
        for (int j=1; j<=m+1; j++){
            if (v[i][j][0]<inf){
                add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),1);
            }
            if (v[i][j][2]<inf){
                add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),1);
            }
        }
    }
}
int swap_seats(int a, int b){
    a++; b++;
    for (int i=pos[a].first; i<=pos[a].first+1; i++){
        for (int j=pos[a].second; j<=pos[a].second+1; j++){
            if (v[i][j][0]<inf){
                add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),-1);
            }
            if (v[i][j][2]<inf){
                add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),-1);
            }
            v[i][j]={inf,inf,inf,inf};
        }
    }
    for (int i=pos[b].first; i<=pos[b].first+1; i++){
        for (int j=pos[b].second; j<=pos[b].second+1; j++){
            if (v[i][j][0]==inf) continue;
            if (v[i][j][0]<inf){
                add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),-1);
            }
            if (v[i][j][2]<inf){
                add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),-1);
            }
            v[i][j]={inf,inf,inf,inf};
        }
    }
    swap(grid[pos[a].first][pos[a].second],grid[pos[b].first][pos[b].second]);
    swap(pos[a],pos[b]);
    for (int i=pos[a].first; i<=pos[a].first+1; i++){
        for (int j=pos[a].second; j<=pos[a].second+1; j++){
            int cnt=0;
            for (int d=-1; d<=0; d++){
                for (int e=-1; e<=0; e++){
                    v[i][j][cnt++]=grid[i+d][j+e];
                }
            }
            sort(v[i][j].begin(),v[i][j].end());
            if (v[i][j][0]<inf){
                add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),1);
            }
            if (v[i][j][2]<inf){
                add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),1);
            }
        }
    }
    for (int i=pos[b].first; i<=pos[b].first+1; i++){
        for (int j=pos[b].second; j<=pos[b].second+1; j++){
            if (v[i][j][0]!=inf) continue;
            int cnt=0;
            for (int d=-1; d<=0; d++){
                for (int e=-1; e<=0; e++){
                    v[i][j][cnt++]=grid[i+d][j+e];
                }
            }
            sort(v[i][j].begin(),v[i][j].end());
            if (v[i][j][0]<inf){
                add(v[i][j][0],(v[i][j][1]==inf?(n+1)*(m+1):v[i][j][1]-1),1);
            }
            if (v[i][j][2]<inf){
                add(v[i][j][2],(v[i][j][3]==inf?(n+1)*(m+1):v[i][j][3]-1),1);
            }
        }
    }
    return cntmn[1]-(n+1)*(m+1)+n*m;
}

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