Submission #274912

#	Time	Username	Problem	Language	Result	Execution time	Memory
274912		Haunted_Cpp	Seats (IOI18_seats)	C++17	5 / 100	4077 ms	86652 KiB

seats

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

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

const int INF = 1e9;
 
int H, W;
vector<int> R, C;

int LO = 0;
int HI = 0;

struct SegmentTree {
  vector<int> mn, mx;
  SegmentTree(const vector<int> &arr) {
    mn.resize(4 * arr.size());
    mx.resize(4 * arr.size());
    build(LO, HI - 1, 0, arr);
  }
  void build(int l, int r, int node, const vector<int>&arr) {
    if (l == r) {
      mn[node] = arr[l];
      mx[node] = arr[l];
      return;
    }
    const int mid = l + (r - l) / 2;
    build(l, mid, 2 * node + 1, arr);
    build(mid + 1, r, 2 * node + 2, arr);
    mn[node] = min(mn[2 * node + 1], mn[2 * node + 2]);
    mx[node] = max(mx[2 * node + 1], mx[2 * node + 2]);
  }
  void modify(int l, int r, int node, int delta, int where) {
    if (l == where && r == where) {
      mn[node] = delta;
      mx[node] = delta;
      return;
    }
    const int mid = l + (r - l) / 2;
    if (where <= mid) modify(l, mid, 2 * node + 1, delta, where);
    if (where >= mid + 1) modify(mid + 1, r, 2 * node + 2, delta, where);
    mn[node] = min(mn[2 * node + 1], mn[2 * node + 2]);
    mx[node] = max(mx[2 * node + 1], mx[2 * node + 2]);
  }
  pair<int, int> query(int ql, int qr, int l, int r, int node) {
    if (l > qr || r < ql) return {INF, -INF};
    if (l >= ql && r <= qr) {
      return {mn[node], mx[node]};
    }
    const int mid = l + (r - l) / 2;
    pair<int, int> esq = {INF, -INF};
    if (ql <= mid) {
      esq = query(ql, qr, l, mid, 2 * node + 1);
    }
    pair<int, int> dir = {INF, -INF};
    if (qr >= mid + 1) {
      dir =  query(ql, qr, mid + 1, r, 2 * node + 2);
    }
    return {min(esq.first, dir.first), max(esq.second, dir.second)};
  }
};

SegmentTree *rows_tree;
SegmentTree *cols_tree;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  ::H = H; ::W = W;
  ::R = R; ::C = C;
  ::HI = H * W;
  rows_tree = new SegmentTree(R);
  cols_tree = new SegmentTree(C);
}

int swap_seats(int a, int b) {
  swap(R[a], R[b]);
  swap(C[a], C[b]);
  rows_tree -> modify(LO, HI - 1, 0, R[a], a); 
  cols_tree -> modify(LO, HI - 1, 0, C[a], a); 
  rows_tree -> modify(LO, HI - 1, 0, R[b], b);
  cols_tree -> modify(LO, HI - 1, 0, C[b], b);
  int res = 0;
  int current_idx = 0;
  int R_min, R_max;
  int C_min, C_max;
  while(current_idx < HI) {
    tie(R_min, R_max) = rows_tree -> query(0, current_idx, LO, HI - 1, 0);
    tie(C_min, C_max) = cols_tree -> query(0, current_idx, LO, HI - 1, 0);
    const int score = (R_max - R_min + 1) * (C_max - C_min + 1);
    if (current_idx + 1 == score) {
      ++res;
      ++current_idx;
    } else {
      current_idx = score - 1;
    }
  }
  return res;
}

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