Submission #1009802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009802		HappyCapybara	Seats (IOI18_seats)	C++17	6 / 100	4062 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;

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);
  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++;
    }
  }
}

int swap_seats(int a, int b){
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  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