Submission #1220523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220523		Malix	Seats (IOI18_seats)	C++20	100 / 100	675 ms	129512 KiB

seats

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vi a,X,Y;
vii arr;
int n,h,w;
vector<ti> st;
//cnt,min,sum

void build(int x,int l,int r){
  if(l==r){
    st[x]={1,a[l],a[l]};
    return;
  }
  int m=(l+r)/2;
  build(2*x,l,m);
  build(2*x+1,m+1,r);
  auto [p1,q1,r1]=st[2*x];
  auto [p2,q2,r2]=st[2*x+1];
  q2+=r1;
  if(q1==q2)st[x]={p1+p2,q1,r1+r2};
  else if(q1<q2)st[x]={p1,q1,r1+r2};
  else st[x]={p2,q2,r1+r2};
}

void update(int x,int l,int r,int p,int v){
  if(l==r){
    st[x]={1,v,v};
    return;
  }
  int m=(l+r)/2;
  if(m>=p)update(2*x,l,m,p,v);
  else update(2*x+1,m+1,r,p,v);
  auto [p1,q1,r1]=st[2*x];
  auto [p2,q2,r2]=st[2*x+1];
  q2+=r1;
  if(q1==q2)st[x]={p1+p2,q1,r1+r2};
  else if(q1<q2)st[x]={p1,q1,r1+r2};
  else st[x]={p2,q2,r1+r2};
}

int solve(int x,int y){
  int ans=0;
  REP(i,x-1,x+1)REP(j,y-1,y+1){
    int cnt=0;
    if(i<0||j<0||arr[i][j]>arr[x][y])cnt++;
    if(i+1>=h||j<0||arr[i+1][j]>arr[x][y])cnt++;
    if(i<0||j+1>=w||arr[i][j+1]>arr[x][y])cnt++;
    if(i+1>=h||j+1>=w||arr[i+1][j+1]>arr[x][y])cnt++;
    if(cnt%2)ans++;
    else ans--;
  }
  return ans;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n=W*H;
  X=R;Y=C;
  h=H;w=W;
  a.resize(n,0);arr.resize(H,vi(W));
  REP(i,0,n)arr[X[i]][Y[i]]=i;
  REP(i,0,n)a[i]=solve(X[i],Y[i]);
  st.resize(4*n+1);
  build(1,0,n-1);
}

int swap_seats(int x, int y) {
  swap(arr[X[x]][Y[x]],arr[X[y]][Y[y]]);
  swap(X[x],X[y]);
  swap(Y[x],Y[y]);
  REP(i,max(0,X[x]-1),min(h,X[x]+2))REP(j,max(0,Y[x]-1),min(w,Y[x]+2)){
    int pos=arr[i][j];
    a[pos]=solve(i,j);
    update(1,0,n-1,pos,a[pos]);
  }
  REP(i,max(0,X[y]-1),min(h,X[y]+2))REP(j,max(0,Y[y]-1),min(w,Y[y]+2)){
    int pos=arr[i][j];
    a[pos]=solve(i,j);
    update(1,0,n-1,pos,a[pos]);
  }
  if(get<1>(st[1])==4)return get<0>(st[1]);
  return 0;
}

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