제출 #585949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585949		Koosha_mv	자리 배치 (IOI18_seats)	C++14	31 / 100	4041 ms	255428 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1e6+99,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

int n,m,A[N],B[N],pfxr[N],sfxr[N],pfxc[N],sfxc[N];
set<int> R[N],C[N];
vector<int> p[N];

void add(int x,int y){
  R[x].insert(p[x][y]);
  C[y].insert(p[x][y]);
}
void del(int x,int y){
  R[x].erase(p[x][y]);
  C[y].erase(p[x][y]);
}
int get(){
  pfxr[0]=pfxc[0]=sfxr[n-1]=sfxc[m-1]=N;
  f(i,0,n){
    minm(pfxr[i],*R[i].begin());
    pfxr[i+1]=pfxr[i];
  }
  f_(i,n-1,0){
    minm(sfxr[i],*R[i].begin());
    sfxr[i-1]=sfxr[i];
  }
  f(i,0,m){
    minm(pfxc[i],*C[i].begin());
    pfxc[i+1]=pfxc[i];
  }
  f_(i,m-1,0){
    minm(sfxc[i],*C[i].begin());
    sfxc[i-1]=sfxc[i];
  }
  int ans=0,mnx=N,mxx=0,mny=N,mxy=0;
  f(i,0,n*m){
    minm(mnx,A[i]);
    maxm(mxx,A[i]);
    minm(mny,B[i]);
    maxm(mxy,B[i]);
    if((mxx-mnx+1)*(mxy-mny+1)==i+1){
      ans++;
    }
    int mn=n*m;
    if(mnx) minm(mn,pfxr[mnx-1]);
    if(mxx+1<n) minm(mn,sfxr[mxx+1]);
    if(mny) minm(mn,pfxc[mny-1]);
    if(mxy+1<m) minm(mn,sfxc[mxy+1]);
    i=max(i,mn-2);
  }
  return ans;
}
void give_initial_chart(int _n, int _m,vector<int> _A,vector<int> _B) {
  n=_n,m=_m;
  f(i,0,n) f(j,0,m) p[i].pb(0);
  f(i,0,n*m){
    A[i]=_A[i],B[i]=_B[i];
    p[A[i]][B[i]]=i;
    R[A[i]].insert(i);
    C[B[i]].insert(i);
  }
}
int swap_seats(int a, int b){
  del(A[a],B[a]);
  del(A[b],B[b]);
  swap(p[A[a]][B[a]],p[A[b]][B[b]]);
  swap(A[a],A[b]);
  swap(B[a],B[b]);
  add(A[a],B[a]);
  add(A[b],B[b]);
  return get();
}
/*
1 6 0
0 5
0 1
0 2
0 3
0 4
0 0
0 5
0 5

1 6 0
0 0
0 3
0 5
0 4
0 1
0 2

1 6 2
0 2
0 3
0 5
0 4
0 1
0 0
0 5
0 5
*/

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