Submission #1009760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009760		HappyCapybara	Seats (IOI18_seats)	C++17	6 / 100	4048 ms	59476 KiB

seats

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

int h, w;
vector<int> r, c, ts, bs, ls, rs, v;
int res = 0;
bool f = true;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
  h = H;
  w = W;
  r = R;
  c = C;
  ts.resize(H*W);
  bs.resize(H*W);
  ls.resize(H*W);
  rs.resize(H*W);
  v.resize(H*W);
}

int swap_seats(int a, int b){
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  if (f){
    f = false;
    v[0] = 1;
    res++;
    ts[0] = r[0]; bs[0] = r[0]; ls[0] = c[0]; rs[0] = c[0];
    for (int i=1; i<h*w; i++){
      ts[i] = min(ts[i-1], r[i]); bs[i] = max(bs[i-1], r[i]); ls[i] = min(ls[i-1], c[i]); rs[i] = max(rs[i-1], c[i]);
      if (i+1 == (bs[i]-ts[i]+1)*(rs[i]-ls[i]+1)){
        v[i] = 1;
        res++;
      }
    }
  }
  else {
    for (int i=max(min(a, b), 1); i<=max(a, b); i++){
      ts[i] = min(ts[i-1], r[i]); bs[i] = max(bs[i-1], r[i]); ls[i] = min(ls[i-1], c[i]); rs[i] = max(rs[i-1], c[i]);
      if (i+1 == (bs[i]-ts[i]+1)*(rs[i]-ls[i]+1)){
        if (!v[i]) res++;
        v[i] = 1;
      }
      else {
        if (v[i]) res--;
        v[i] = 0;
      }
    }
  }
  return res;
}

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