Submission #1239014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239014		noyancanturk	Seats (IOI18_seats)	C++20	17 / 100	4096 ms	94376 KiB

seats

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

const int lim=1e6+100;

int n,h,w;
vector<int>v[lim];

vector<int>r,c;

int ok[lim];
  int ans=0,mxc[lim],mxr[lim],mnr[lim],mnc[lim];

void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
  n=H*W;
  h=H;
  w=W;
  for(int i=0;i<H;i++){
    v[i].resize(W);
  }
  r=R,c=C;
  for(int i=0;i<n;i++){
    v[r[i]][c[i]]=i;
  }
  for(int i=0;i<n;i++){
    mxc[i]=mnc[i]=c[i];
    mxr[i]=mnr[i]=r[i];
    if(i){
      mxc[i]=max(mxc[i],mxc[i-1]);
      mxr[i]=max(mxr[i],mxr[i-1]);
      mnc[i]=min(mnc[i],mnc[i-1]);
      mnr[i]=min(mnr[i],mnr[i-1]);
    }
    if(i+1==(mxc[i]-mnc[i]+1)*(mxr[i]-mnr[i]+1)){
      ok[i]=1;
      ans++;
    }
  }
}

int swap_seats(int x,int y){
  if(y<x)swap(x,y);
  swap(r[x],r[y]);
  swap(c[x],c[y]);
  for(int i=x;i<=y;i++){
    mxc[i]=mnc[i]=c[i];
    mxr[i]=mnr[i]=r[i];
    if(i){
      mxc[i]=max(mxc[i],mxc[i-1]);
      mxr[i]=max(mxr[i],mxr[i-1]);
      mnc[i]=min(mnc[i],mnc[i-1]);
      mnr[i]=min(mnr[i],mnr[i-1]);
    }
    if(i+1==(mxc[i]-mnc[i]+1)*(mxr[i]-mnr[i]+1)){
      ans+=1-ok[i];
      ok[i]=1;
    }else{
      ans-=ok[i];
      ok[i]=0;
    }
  }
  return ans;
}

// std::vector<int> r;

// void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
//   r = R;
// }

// int swap_seats(int a, int b) {
//   return r[a];
// }

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