oj.uz

Submission #835115

# Submission time Handle Problem Language Result Execution time Memory
835115 2023-08-23T08:39:53 Z Johann Seats (IOI18_seats) C++14
0 / 100
 235 ms 98984 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;
  vi mini, maxi;
  void init(vi &A)
  {
    size = 1;
    while (size < sz(A))
      size *= 2;
    mini.assign(2 * size, INT_MAX);
    maxi.assign(2 * size, INT_MIN);
    for (int i = 0; i < sz(A); ++i)
      mini[i + size] = maxi[i + size] = A[i];
    for (int i = sz(A) - 1; i > 0; --i)
      maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]),
      mini[i] = min(mini[2 * i], mini[2 * i + 1]);
  }
  void set(int i, int v)
  {
    i += size;
    mini[i] = maxi[i] = v;
    while (i >>= 1 > 0)
      maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]),
      mini[i] = min(mini[2 * i], mini[2 * i + 1]);
  }
  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 {mini[x], maxi[x]};
    if (r <= lx || rx <= l)
      return {INT_MAX, INT_MIN};
    int m = (lx + rx) / 2;
    int mini1, mini2, maxi1, maxi2;
    tie(mini1, maxi1) = query(l, r, 2 * x, lx, m);
    tie(mini2, maxi2) = query(l, r, 2 * x + 1, m, rx);
    return {min(mini1, mini2), max(maxi1, maxi2)};
  }
};
segtree segR;
segtree segC;

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

int swap_seats(int a, int 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 rmax = R[0], rmin = R[0];
  int cmax = C[0], cmin = C[0];
  int ans = 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)
      ++ans, ++k;
    else
    {
      assert(area - 1 > k);
      k = area - 1;
    }
  }

  return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 56652 KB Output is correct
2 Runtime error 235 ms 98984 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 2004 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1360 KB Output is correct
2 Runtime error 8 ms 1236 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -