oj.uz

Submission #835727

# Submission time Handle Problem Language Result Execution time Memory
835727 2023-08-23T18:34:10 Z Johann Seats (IOI18_seats) C++14
17 / 100
 4000 ms 76584 KB 
#include "seats.h"
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int H, W;
std::vector<int> R, C;
struct segtree
{
  int size;
  vpii arr;
  const pii NEUTRAL = {1 << 30, -(1 << 30)};
  void init(vi &A)
  {
    size = 1;
    while (size < sz(A))
      size *= 2;
    arr.assign(2 * size, NEUTRAL);
    for (int i = 0; i < sz(A); ++i)
      arr[i + size] = {A[i], A[i]};
    for (int i = size - 1; i > 0; --i)
      arr[i] = combine(arr[2 * i], arr[2 * i + 1]);
  }
  pii combine(const pii &a, const pii &b)
  {
    return {min(a.first, b.first), max(a.second, b.second)};
  }
  void set(int i, int v)
  {
    i += size;
    arr[i] = {v, v};
    i /= 2;
    while (i > 0)
    {
      arr[i] = combine(arr[2 * i], arr[2 * i + 1]);
      i /= 2;
    }
  }
  pii query(int l, int r) { return query(l, r, 1, 0, size); }
  pii query(int l, int r, int x, int lx, int rx)
  {
    if (l <= lx && rx <= r)
      return arr[x];
    if (r <= lx || rx <= l)
      return NEUTRAL;
    int m = (lx + rx) / 2;
    pii left = query(l, r, 2 * x, lx, m);
    pii right = query(l, r, 2 * x + 1, m, rx);
    return combine(left, right);
  }
};
segtree segR;
segtree segC;

struct fenwick
{
  vi arr;
  void init(int size)
  {
    arr.assign(size + 1, 0);
  }
  void add(int i, int v)
  {
    ++i;
    while (i < sz(arr))
      arr[i] += v, i += i & (~i + 1);
  }
  int query(int l, int r) { return query(r - 1) - ((l > 0) ? query(l - 1) : 0); }
  int query(int i)
  {
    ++i;
    int ans = 0;
    while (i > 0)
      ans += arr[i], i -= i & (~i + 1);
    return ans;
  }
};
fenwick fen;

void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C)
{
  H = _H, W = _W;
  R = _R, C = _C;
  segR.init(R), segC.init(C);
  fen.init(H * W);

  int rmax = R[0], rmin = R[0];
  int cmax = C[0], cmin = C[0];
  int k = 0;
  while (k < H * W)
  {
    tie(rmin, rmax) = segR.query(0, k + 1);
    tie(cmin, cmax) = segC.query(0, k + 1);
    int area = (rmax - rmin + 1) * (cmax - cmin + 1);
    if (area == k + 1)
      fen.add(k, 1), ++k;
    else
    {
      assert(area - 1 > k);
      k = area - 1;
    }
  }
}

int swap_seats(int a, int b)
{
  if (a > b)
    swap(a, b);
  swap(R[a], R[b]), swap(C[a], C[b]);
  segR.set(a, R[a]);
  segC.set(a, C[a]);
  segR.set(b, R[b]);
  segC.set(b, C[b]);

  int rmin, rmax, cmin, cmax;
  tie(rmin, rmax) = segR.query(0, a + 1);
  tie(cmin, cmax) = segC.query(0, a + 1);
  for (int k = a; k < b + 1; ++k)
  {
    if (fen.query(k, k + 1))
      fen.add(k, -1);
    rmax = max(rmax, R[k]);
    rmin = min(rmin, R[k]);
    cmax = max(cmax, C[k]);
    cmin = min(cmin, C[k]);
    int area = (rmax - rmin + 1) * (cmax - cmin + 1);
    if (area == k + 1)
      fen.add(k, 1);
  }

  return fen.query(0, H * W);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 436 KB Output is correct
7 Correct 3 ms 436 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 396 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 4 ms 436 KB Output is correct
12 Correct 4 ms 400 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 436 KB Output is correct
7 Correct 3 ms 436 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 396 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 4 ms 436 KB Output is correct
12 Correct 4 ms 400 KB Output is correct
13 Correct 189 ms 1312 KB Output is correct
14 Correct 168 ms 1312 KB Output is correct
15 Correct 166 ms 1308 KB Output is correct
16 Correct 270 ms 1304 KB Output is correct
17 Correct 173 ms 1308 KB Output is correct
18 Correct 171 ms 1304 KB Output is correct
19 Correct 192 ms 1304 KB Output is correct
20 Correct 220 ms 1308 KB Output is correct
21 Correct 218 ms 1364 KB Output is correct
22 Correct 206 ms 1300 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4056 ms 76416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 1316 KB Output is correct
2 Correct 307 ms 8120 KB Output is correct
3 Correct 539 ms 76440 KB Output is correct
4 Correct 555 ms 76452 KB Output is correct
5 Correct 1124 ms 76584 KB Output is correct
6 Correct 540 ms 76492 KB Output is correct
7 Correct 652 ms 76532 KB Output is correct
8 Correct 559 ms 76460 KB Output is correct
9 Correct 567 ms 76472 KB Output is correct
10 Correct 540 ms 76456 KB Output is correct
11 Correct 755 ms 76532 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2000 KB Output is correct
2 Correct 21 ms 1992 KB Output is correct
3 Correct 33 ms 1920 KB Output is correct
4 Correct 179 ms 2028 KB Output is correct
5 Correct 1665 ms 2760 KB Output is correct
6 Execution timed out 4072 ms 71704 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 436 KB Output is correct
7 Correct 3 ms 436 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 4 ms 396 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 4 ms 436 KB Output is correct
12 Correct 4 ms 400 KB Output is correct
13 Correct 189 ms 1312 KB Output is correct
14 Correct 168 ms 1312 KB Output is correct
15 Correct 166 ms 1308 KB Output is correct
16 Correct 270 ms 1304 KB Output is correct
17 Correct 173 ms 1308 KB Output is correct
18 Correct 171 ms 1304 KB Output is correct
19 Correct 192 ms 1304 KB Output is correct
20 Correct 220 ms 1308 KB Output is correct
21 Correct 218 ms 1364 KB Output is correct
22 Correct 206 ms 1300 KB Output is correct
23 Execution timed out 4056 ms 76416 KB Time limit exceeded
24 Halted 0 ms 0 KB -