Submission #282664

#	Time	Username	Problem	Language	Result	Execution time	Memory
282664		Haunted_Cpp	Seats (IOI18_seats)	C++17	25 / 100	4064 ms	72312 KiB

seats

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

const int INF = 1e9;

struct SegmentTree {
  vector<int> mn, mx;
  const int n;
  SegmentTree(const vector<int> &arr) : n(arr.size()) {
    mn = mx = vector<int>(2 * n);
    for (int i = 0; i < n; i++) mn[i + n] = mx[i + n] = arr[i];
    for (int i = n - 1; i > 0; i--) {
      mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
      mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
    }
  }
  void modify(int where, int delta) {
    where += n;
    mn[where] = mx[where] = delta;
    for (; where > 1; where >>= 1) {
      mn[where >> 1] = min(mn[where], mn[where ^ 1]);
      mx[where >> 1] = max(mx[where], mx[where ^ 1]);
    }
  }
  pair<int, int> rmq(int l, int r) {
    pair<int, int> res = {INF, -INF};
    l += n;
    r += n;
    for(; l <= r; l >>= 1, r >>= 1) {
      if (l & 1) {
        res.first = min(res.first, mn[l]);
        res.second = max(res.second, mx[l]);
        ++l;
      }
      if (r & 1 ^ 1) {
        res.first = min(res.first, mn[r]);
        res.second = max(res.second, mx[r]);
        --r;
      }
    }
    return res;
  }
};

int H, W;
vector<int> R, C;
SegmentTree *rows, *cols;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  ::H = H; ::W = W;
  ::R = R; ::C = C;
  rows = new SegmentTree(R);
  cols = new SegmentTree(C);
}

int swap_seats(int a, int b) {
  swap(R[a], R[b]);
  swap(C[a], C[b]);
  rows -> modify(a, R[a]);
  rows -> modify(b, R[b]);
  cols -> modify(a, C[a]);
  cols -> modify(b, C[b]);
  int idx = 0, res = 0;
  int R_min, R_max, C_min, C_max;
  while(idx < H * W) {
    tie(R_min, R_max) = rows -> rmq(0, idx);
    tie(C_min, C_max) = cols -> rmq(0, idx);
    int score = (R_max - R_min + 1) * (C_max - C_min + 1);
    if (score == idx + 1) {
      ++res;
      ++idx;
    } else {
      idx = score - 1;
    }
  }
  return res;
}

Compilation message (stderr)

seats.cpp: In member function 'std::pair<int, int> SegmentTree::rmq(int, int)':
seats.cpp:35:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   35 |       if (r & 1 ^ 1) {
      |           ~~^~~

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