Submission #580552

#	Time	Username	Problem	Language	Result	Execution time	Memory
580552		Vanilla	Seats (IOI18_seats)	C++17	17 / 100	4069 ms	59456 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
typedef long long int64;
using namespace std;
vector<int> r,c;
const int maxn = 1e6 + 2;
int ll [maxn], rr[maxn], uu[maxn], dd[maxn], rs[maxn];
int n = 0, m = 0;

int query (int x) {
  if (x == 0) return 1;
  int r = 1;
  for (; x >= 1; x-=x & -x) r+=rs[x];
  return r;
}

void upd (int x, int d) {
  for (; x < maxn; x+=x & -x) rs[x]+=d;
} 

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  r = R, c = C, n = H, m = W;
  ll[0] = c[0], rr[0] = c[0], uu[0] = r[0], dd[0] = r[0];
  for (int i = 1; i < n * m; i++){
    ll[i] = min(ll[i-1], c[i]);
    rr[i] = max(rr[i-1], c[i]);
    uu[i] = min(uu[i-1], r[i]);
    dd[i] = max(dd[i-1], r[i]);
    // cout << i << " " << ll << " " << rr << " " << uu << " " << dd << "\n";
    if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) == i + 1) upd(i, 1);
  }

}

int swap_seats(int a, int b) {
  swap(r[a], r[b]);
  swap(c[a], c[b]);
  if (a > b) swap(a,b);
  if (a == 0) ll[0] = c[0], rr[0] = c[0], uu[0] = r[0], dd[0] = r[0];
  for (int i = max(a, 1); i <= b; i++){
    if (i == 0) continue;
    ll[i] = min(ll[i-1], c[i]);
    rr[i] = max(rr[i-1], c[i]);
    uu[i] = min(uu[i-1], r[i]);
    dd[i] = max(dd[i-1], r[i]);
    // cout << i << " " << ll << " " << rr << " " << uu << " " << dd << "\n";
    // if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) == i + 1) cout << i << " ";
    if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) == i + 1 && query(i) - query(i - 1) != 1) upd(i, 1);
    if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) != i + 1 && query(i) - query(i - 1) == 1) upd(i, -1);
  }
  return query(maxn - 1);
}

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