oj.uz

Submission #888936

# Submission time Handle Problem Language Result Execution time Memory
888936 2023-12-18T12:27:37 Z nguyentunglam Seats (IOI18_seats) C++17
100 / 100
 2744 ms 131408 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()

using namespace std;

const int N = 1e6 + 10, M = 1010;

int r[N], c[N], order[4];

vector<vector<int> > a;

int h, w;

int f[N << 2], g[N << 2], lazy[N << 2];

void push(int s, int l, int r) {
  if (!lazy[s]) return;
  f[s] += lazy[s];
  if (l != r) {
    lazy[s << 1] += lazy[s];
    lazy[s << 1 | 1] += lazy[s];
  }
  lazy[s] = 0;
}

void up(int s, int l, int r, int from, int to, int val) {
  push(s, l, r);
  if (l > to || r < from) return;
  if (from <= l && r <= to) {
    lazy[s] = val;
    push(s, l, r);
    return;
  }
  int mid = l + r >> 1;
  up(s << 1, l, mid, from, to, val);
  up(s << 1 | 1, mid + 1, r, from, to, val);
  f[s] = min(f[s << 1], f[s << 1 | 1]);
  g[s] = (f[s] == f[s << 1]) * g[s << 1] + (f[s] == f[s << 1 | 1]) * g[s << 1 | 1];
}

void update (int x, int y, int val) {
  order[0] = a[x][y];
  order[1] = a[x + 1][y];
  order[2] = a[x][y + 1];
  order[3] = a[x + 1][y + 1];
  order[4] = h * w + 1;
  sort(order, order + 4);
  int one = 0, three = 0, cnt = 0;
  for(int i = 0; i < 4; i++) {
    cnt += order[i] > 0;
    if (cnt == 1) up(1, 1, h * w, order[i], order[i + 1] - 1, val);
    if (cnt == 3) up(1, 1, h * w, order[i], order[i + 1] - 1, val * 5);
  }
}

void give_initial_chart(int _h, int _w, vector<int> _r, vector<int> _c) {
  h = _h; w = _w;
  a = vector<vector<int> > (h + 2, vector<int> (w + 2));
  for(int i = 1; i <= h * w; i++) {
    r[i] = _r[i - 1] + 1, c[i] = _c[i - 1] + 1;
    a[r[i]][c[i]] = i;
  }

  for(int i = 1; i <= 4 * h * w; i++) g[i] = 1;

  for(int i = 0; i <= h; i++) for(int j = 0; j <= w; j++) update(i, j, 1);

//   for(int i = 0; i < h * w; i++) cout << r[i] << " " << c[i] << endl;
}

void change (int x, int y, int val) {
  update(x - 1, y - 1, val);
  update(x, y - 1, val);
  update(x - 1, y, val);
  update(x, y, val);
}

int swap_seats(int x, int y) {
  ++x; ++y;

  change(r[x], c[x], -1);
  a[r[x]][c[x]] = y;
  change(r[x], c[x], 1);

  change(r[y], c[y], -1);
  a[r[y]][c[y]] = x;
  change(r[y], c[y], 1);

  swap(r[x], r[y]);
  swap(c[x], c[y]);

  return g[1];
}

#ifdef ngu
int main() {
   freopen ("task.inp", "r", stdin);
   freopen ("task.out", "w", stdout);

   int _h, _w; cin >> _h >> _w;
   vector<int> _r(_h * _w), _c(_h * _w);
   for(int i = 0; i < _h; i++) for(int j = 0; j < _w; j++) {
      int x; cin >> x;
      _r[x] = i;
      _c[x] = j;
   }

   give_initial_chart(_h, _w, _r, _c);

   int q; cin >> q;

   while (q--) {
      int a, b; cin >> a >> b;
      cout << swap_seats(a, b) << endl;
   }
}
#endif // ngu

Compilation message

seats.cpp: In function 'void up(int, int, int, int, int, int)':
seats.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~
seats.cpp: In function 'void update(int, int, int)':
seats.cpp:52:7: warning: unused variable 'one' [-Wunused-variable]
   52 |   int one = 0, three = 0, cnt = 0;
      |       ^~~
seats.cpp:52:16: warning: unused variable 'three' [-Wunused-variable]
   52 |   int one = 0, three = 0, cnt = 0;
      |                ^~~~~
seats.cpp:50:10: warning: array subscript 4 is above array bounds of 'int [4]' [-Warray-bounds]
   50 |   order[4] = h * w + 1;
      |   ~~~~~~~^
seats.cpp:12:17: note: while referencing 'order'
   12 | int r[N], c[N], order[4];
      |                 ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8540 KB Output is correct
2 Correct 16 ms 8720 KB Output is correct
3 Correct 30 ms 8540 KB Output is correct
4 Correct 16 ms 8720 KB Output is correct
5 Correct 14 ms 8540 KB Output is correct
6 Correct 24 ms 8744 KB Output is correct
7 Correct 31 ms 8712 KB Output is correct
8 Correct 22 ms 8540 KB Output is correct
9 Correct 22 ms 8720 KB Output is correct
10 Correct 25 ms 8536 KB Output is correct
11 Correct 23 ms 8536 KB Output is correct
12 Correct 14 ms 8540 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8540 KB Output is correct
2 Correct 16 ms 8720 KB Output is correct
3 Correct 30 ms 8540 KB Output is correct
4 Correct 16 ms 8720 KB Output is correct
5 Correct 14 ms 8540 KB Output is correct
6 Correct 24 ms 8744 KB Output is correct
7 Correct 31 ms 8712 KB Output is correct
8 Correct 22 ms 8540 KB Output is correct
9 Correct 22 ms 8720 KB Output is correct
10 Correct 25 ms 8536 KB Output is correct
11 Correct 23 ms 8536 KB Output is correct
12 Correct 14 ms 8540 KB Output is correct
13 Correct 60 ms 8796 KB Output is correct
14 Correct 75 ms 9048 KB Output is correct
15 Correct 43 ms 9280 KB Output is correct
16 Correct 29 ms 9564 KB Output is correct
17 Correct 51 ms 9224 KB Output is correct
18 Correct 45 ms 9052 KB Output is correct
19 Correct 43 ms 9048 KB Output is correct
20 Correct 42 ms 9556 KB Output is correct
21 Correct 30 ms 9304 KB Output is correct
22 Correct 30 ms 9708 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1715 ms 64452 KB Output is correct
2 Correct 870 ms 80608 KB Output is correct
3 Correct 829 ms 80724 KB Output is correct
4 Correct 760 ms 80528 KB Output is correct
5 Correct 773 ms 80608 KB Output is correct
6 Correct 734 ms 80416 KB Output is correct
7 Correct 775 ms 80356 KB Output is correct
8 Correct 818 ms 80712 KB Output is correct
9 Correct 816 ms 80464 KB Output is correct
10 Correct 772 ms 80800 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8796 KB Output is correct
2 Correct 122 ms 15956 KB Output is correct
3 Correct 767 ms 80548 KB Output is correct
4 Correct 1667 ms 80616 KB Output is correct
5 Correct 707 ms 88060 KB Output is correct
6 Correct 1746 ms 131408 KB Output is correct
7 Correct 757 ms 82984 KB Output is correct
8 Correct 816 ms 80724 KB Output is correct
9 Correct 784 ms 80752 KB Output is correct
10 Correct 795 ms 85284 KB Output is correct
11 Correct 812 ms 102644 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 9652 KB Output is correct
2 Correct 79 ms 9544 KB Output is correct
3 Correct 129 ms 9680 KB Output is correct
4 Correct 259 ms 9676 KB Output is correct
5 Correct 324 ms 11024 KB Output is correct
6 Correct 1170 ms 89208 KB Output is correct
7 Correct 1375 ms 89360 KB Output is correct
8 Correct 1136 ms 89232 KB Output is correct
9 Correct 2312 ms 89360 KB Output is correct
10 Correct 1072 ms 89100 KB Output is correct
11 Correct 1078 ms 89616 KB Output is correct
12 Correct 1022 ms 89608 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8540 KB Output is correct
2 Correct 16 ms 8720 KB Output is correct
3 Correct 30 ms 8540 KB Output is correct
4 Correct 16 ms 8720 KB Output is correct
5 Correct 14 ms 8540 KB Output is correct
6 Correct 24 ms 8744 KB Output is correct
7 Correct 31 ms 8712 KB Output is correct
8 Correct 22 ms 8540 KB Output is correct
9 Correct 22 ms 8720 KB Output is correct
10 Correct 25 ms 8536 KB Output is correct
11 Correct 23 ms 8536 KB Output is correct
12 Correct 14 ms 8540 KB Output is correct
13 Correct 60 ms 8796 KB Output is correct
14 Correct 75 ms 9048 KB Output is correct
15 Correct 43 ms 9280 KB Output is correct
16 Correct 29 ms 9564 KB Output is correct
17 Correct 51 ms 9224 KB Output is correct
18 Correct 45 ms 9052 KB Output is correct
19 Correct 43 ms 9048 KB Output is correct
20 Correct 42 ms 9556 KB Output is correct
21 Correct 30 ms 9304 KB Output is correct
22 Correct 30 ms 9708 KB Output is correct
23 Correct 1715 ms 64452 KB Output is correct
24 Correct 870 ms 80608 KB Output is correct
25 Correct 829 ms 80724 KB Output is correct
26 Correct 760 ms 80528 KB Output is correct
27 Correct 773 ms 80608 KB Output is correct
28 Correct 734 ms 80416 KB Output is correct
29 Correct 775 ms 80356 KB Output is correct
30 Correct 818 ms 80712 KB Output is correct
31 Correct 816 ms 80464 KB Output is correct
32 Correct 772 ms 80800 KB Output is correct
33 Correct 59 ms 8796 KB Output is correct
34 Correct 122 ms 15956 KB Output is correct
35 Correct 767 ms 80548 KB Output is correct
36 Correct 1667 ms 80616 KB Output is correct
37 Correct 707 ms 88060 KB Output is correct
38 Correct 1746 ms 131408 KB Output is correct
39 Correct 757 ms 82984 KB Output is correct
40 Correct 816 ms 80724 KB Output is correct
41 Correct 784 ms 80752 KB Output is correct
42 Correct 795 ms 85284 KB Output is correct
43 Correct 812 ms 102644 KB Output is correct
44 Correct 43 ms 9652 KB Output is correct
45 Correct 79 ms 9544 KB Output is correct
46 Correct 129 ms 9680 KB Output is correct
47 Correct 259 ms 9676 KB Output is correct
48 Correct 324 ms 11024 KB Output is correct
49 Correct 1170 ms 89208 KB Output is correct
50 Correct 1375 ms 89360 KB Output is correct
51 Correct 1136 ms 89232 KB Output is correct
52 Correct 2312 ms 89360 KB Output is correct
53 Correct 1072 ms 89100 KB Output is correct
54 Correct 1078 ms 89616 KB Output is correct
55 Correct 1022 ms 89608 KB Output is correct
56 Correct 107 ms 10192 KB Output is correct
57 Correct 265 ms 10548 KB Output is correct
58 Correct 408 ms 10696 KB Output is correct
59 Correct 1479 ms 81200 KB Output is correct
60 Correct 2744 ms 81404 KB Output is correct
61 Correct 1352 ms 81576 KB Output is correct
62 Correct 1157 ms 85448 KB Output is correct
63 Correct 2606 ms 84152 KB Output is correct
64 Correct 1586 ms 82380 KB Output is correct
65 Correct 1433 ms 81668 KB Output is correct
66 Correct 1548 ms 81492 KB Output is correct
67 Correct 1594 ms 86048 KB Output is correct
68 Correct 1251 ms 95872 KB Output is correct
69 Correct 2439 ms 105008 KB Output is correct