// M
#include<bits/stdc++.h>
#include "seats.h"
#define pb push_back
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int MXN = 1e6 + 10;
int n, m, k, R[MXN], C[MXN], PS[MXN];
int MN[MXN * 4], LZ[MXN * 4], Cnt[MXN * 4];
vector < vector < int > > A;
void Build(int id = 1, int l = 0, int r = k)
{
if (r - l < 2)
{
Cnt[id] = 1;
MN[id] = PS[l];
return ;
}
Build(lc, l, md);
Build(rc, md, r);
MN[id] = min(MN[lc], MN[rc]);
Cnt[id] = 0;
if (MN[id] == MN[lc]) Cnt[id] += Cnt[lc];
if (MN[id] == MN[rc]) Cnt[id] += Cnt[rc];
}
inline void Shift(int id)
{
MN[lc] += LZ[id];
MN[rc] += LZ[id];
LZ[lc] += LZ[id];
LZ[rc] += LZ[id];
LZ[id] = 0;
}
int le, ri, val;
void Add(int id = 1, int l = 0, int r = k)
{
if (ri <= l || r <= le)
return ;
if (le <= l && r <= ri)
{
MN[id] += val;
LZ[id] += val;
return ;
}
Shift(id);
Add(lc, l, md);
Add(rc, md, r);
MN[id] = min(MN[lc], MN[rc]);
Cnt[id] = 0;
if (MN[id] == MN[lc]) Cnt[id] += Cnt[lc];
if (MN[id] == MN[rc]) Cnt[id] += Cnt[rc];
}
inline void Do(int i, int j, int _val)
{
vector < int > tmp = {A[i][j], A[i + 1][j], A[i][j + 1], A[i + 1][j + 1]};
sort(tmp.begin(), tmp.end());
le = tmp[0]; ri = tmp[1]; val = _val;
Add();
le = tmp[2]; ri = tmp[3]; val = _val;
Add();
}
void give_initial_chart(int _H, int _W, vector < int > _R, vector < int > _C)
{
n = _H; m = _W;
for (int i = 0; i < n * m; i ++)
R[i] = _R[i], C[i] = _C[i];
k = n * m;
for (int i = 0; i <= n + 1; i ++)
A.pb(vector < int > (m + 2, k));
for (int i = 0; i < k; i ++)
R[i] ++, C[i] ++;
for (int i = 0; i < k; i ++)
A[R[i]][C[i]] = i;
for (int i = 0; i <= n; i ++)
for (int j = 0; j <= m; j ++)
{
vector < int > tmp = {A[i][j], A[i + 1][j], A[i][j + 1], A[i + 1][j + 1]};
sort(tmp.begin(), tmp.end());
PS[tmp[0]] ++; PS[tmp[1]] --;
PS[tmp[2]] ++; PS[tmp[3]] --;
}
for (int i = 1; i < k; i ++)
PS[i] += PS[i - 1];
Build();
}
int swap_seats(int a, int b)
{
vector < pair < int , int > > vec;
for (int dx = -1; dx <= 0; dx ++)
for (int dy = -1; dy <= 0; dy ++)
vec.push_back({R[a] + dx, C[a] + dy}), vec.push_back({R[b] + dx, C[b] + dy});
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
for (auto X : vec)
Do(X.first, X.second, -1);
swap(R[a], R[b]);
swap(C[a], C[b]);
swap(A[R[a]][C[a]], A[R[b]][C[b]]);
for (auto X : vec)
Do(X.first, X.second, 1);
assert(MN[1] == 4);
return Cnt[1];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
512 KB |
Output is correct |
2 |
Correct |
34 ms |
508 KB |
Output is correct |
3 |
Correct |
39 ms |
504 KB |
Output is correct |
4 |
Correct |
25 ms |
508 KB |
Output is correct |
5 |
Correct |
25 ms |
500 KB |
Output is correct |
6 |
Correct |
33 ms |
504 KB |
Output is correct |
7 |
Correct |
37 ms |
504 KB |
Output is correct |
8 |
Correct |
33 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
504 KB |
Output is correct |
10 |
Correct |
36 ms |
504 KB |
Output is correct |
11 |
Correct |
34 ms |
512 KB |
Output is correct |
12 |
Correct |
23 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
512 KB |
Output is correct |
2 |
Correct |
34 ms |
508 KB |
Output is correct |
3 |
Correct |
39 ms |
504 KB |
Output is correct |
4 |
Correct |
25 ms |
508 KB |
Output is correct |
5 |
Correct |
25 ms |
500 KB |
Output is correct |
6 |
Correct |
33 ms |
504 KB |
Output is correct |
7 |
Correct |
37 ms |
504 KB |
Output is correct |
8 |
Correct |
33 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
504 KB |
Output is correct |
10 |
Correct |
36 ms |
504 KB |
Output is correct |
11 |
Correct |
34 ms |
512 KB |
Output is correct |
12 |
Correct |
23 ms |
512 KB |
Output is correct |
13 |
Correct |
90 ms |
1144 KB |
Output is correct |
14 |
Correct |
101 ms |
1272 KB |
Output is correct |
15 |
Correct |
56 ms |
1152 KB |
Output is correct |
16 |
Correct |
44 ms |
1596 KB |
Output is correct |
17 |
Correct |
81 ms |
1184 KB |
Output is correct |
18 |
Correct |
72 ms |
1152 KB |
Output is correct |
19 |
Correct |
64 ms |
1152 KB |
Output is correct |
20 |
Correct |
55 ms |
1408 KB |
Output is correct |
21 |
Correct |
44 ms |
1152 KB |
Output is correct |
22 |
Correct |
61 ms |
1596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
739 ms |
48864 KB |
Output is correct |
2 |
Correct |
579 ms |
48608 KB |
Output is correct |
3 |
Correct |
591 ms |
48736 KB |
Output is correct |
4 |
Correct |
588 ms |
48692 KB |
Output is correct |
5 |
Correct |
556 ms |
48600 KB |
Output is correct |
6 |
Correct |
602 ms |
48628 KB |
Output is correct |
7 |
Correct |
626 ms |
48612 KB |
Output is correct |
8 |
Correct |
586 ms |
48628 KB |
Output is correct |
9 |
Correct |
569 ms |
48608 KB |
Output is correct |
10 |
Correct |
588 ms |
48740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
1152 KB |
Output is correct |
2 |
Correct |
141 ms |
5716 KB |
Output is correct |
3 |
Correct |
563 ms |
48608 KB |
Output is correct |
4 |
Correct |
878 ms |
48608 KB |
Output is correct |
5 |
Correct |
577 ms |
56548 KB |
Output is correct |
6 |
Correct |
872 ms |
99544 KB |
Output is correct |
7 |
Correct |
570 ms |
51300 KB |
Output is correct |
8 |
Correct |
575 ms |
48740 KB |
Output is correct |
9 |
Correct |
607 ms |
49056 KB |
Output is correct |
10 |
Correct |
621 ms |
53392 KB |
Output is correct |
11 |
Correct |
626 ms |
72084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
1396 KB |
Output is correct |
2 |
Correct |
154 ms |
1652 KB |
Output is correct |
3 |
Correct |
229 ms |
1396 KB |
Output is correct |
4 |
Correct |
304 ms |
1652 KB |
Output is correct |
5 |
Correct |
490 ms |
2228 KB |
Output is correct |
6 |
Correct |
1316 ms |
57592 KB |
Output is correct |
7 |
Correct |
1265 ms |
57700 KB |
Output is correct |
8 |
Correct |
1231 ms |
57588 KB |
Output is correct |
9 |
Correct |
1500 ms |
57576 KB |
Output is correct |
10 |
Correct |
1115 ms |
57704 KB |
Output is correct |
11 |
Correct |
1138 ms |
57704 KB |
Output is correct |
12 |
Correct |
1105 ms |
57728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
512 KB |
Output is correct |
2 |
Correct |
34 ms |
508 KB |
Output is correct |
3 |
Correct |
39 ms |
504 KB |
Output is correct |
4 |
Correct |
25 ms |
508 KB |
Output is correct |
5 |
Correct |
25 ms |
500 KB |
Output is correct |
6 |
Correct |
33 ms |
504 KB |
Output is correct |
7 |
Correct |
37 ms |
504 KB |
Output is correct |
8 |
Correct |
33 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
504 KB |
Output is correct |
10 |
Correct |
36 ms |
504 KB |
Output is correct |
11 |
Correct |
34 ms |
512 KB |
Output is correct |
12 |
Correct |
23 ms |
512 KB |
Output is correct |
13 |
Correct |
90 ms |
1144 KB |
Output is correct |
14 |
Correct |
101 ms |
1272 KB |
Output is correct |
15 |
Correct |
56 ms |
1152 KB |
Output is correct |
16 |
Correct |
44 ms |
1596 KB |
Output is correct |
17 |
Correct |
81 ms |
1184 KB |
Output is correct |
18 |
Correct |
72 ms |
1152 KB |
Output is correct |
19 |
Correct |
64 ms |
1152 KB |
Output is correct |
20 |
Correct |
55 ms |
1408 KB |
Output is correct |
21 |
Correct |
44 ms |
1152 KB |
Output is correct |
22 |
Correct |
61 ms |
1596 KB |
Output is correct |
23 |
Correct |
739 ms |
48864 KB |
Output is correct |
24 |
Correct |
579 ms |
48608 KB |
Output is correct |
25 |
Correct |
591 ms |
48736 KB |
Output is correct |
26 |
Correct |
588 ms |
48692 KB |
Output is correct |
27 |
Correct |
556 ms |
48600 KB |
Output is correct |
28 |
Correct |
602 ms |
48628 KB |
Output is correct |
29 |
Correct |
626 ms |
48612 KB |
Output is correct |
30 |
Correct |
586 ms |
48628 KB |
Output is correct |
31 |
Correct |
569 ms |
48608 KB |
Output is correct |
32 |
Correct |
588 ms |
48740 KB |
Output is correct |
33 |
Correct |
83 ms |
1152 KB |
Output is correct |
34 |
Correct |
141 ms |
5716 KB |
Output is correct |
35 |
Correct |
563 ms |
48608 KB |
Output is correct |
36 |
Correct |
878 ms |
48608 KB |
Output is correct |
37 |
Correct |
577 ms |
56548 KB |
Output is correct |
38 |
Correct |
872 ms |
99544 KB |
Output is correct |
39 |
Correct |
570 ms |
51300 KB |
Output is correct |
40 |
Correct |
575 ms |
48740 KB |
Output is correct |
41 |
Correct |
607 ms |
49056 KB |
Output is correct |
42 |
Correct |
621 ms |
53392 KB |
Output is correct |
43 |
Correct |
626 ms |
72084 KB |
Output is correct |
44 |
Correct |
109 ms |
1396 KB |
Output is correct |
45 |
Correct |
154 ms |
1652 KB |
Output is correct |
46 |
Correct |
229 ms |
1396 KB |
Output is correct |
47 |
Correct |
304 ms |
1652 KB |
Output is correct |
48 |
Correct |
490 ms |
2228 KB |
Output is correct |
49 |
Correct |
1316 ms |
57592 KB |
Output is correct |
50 |
Correct |
1265 ms |
57700 KB |
Output is correct |
51 |
Correct |
1231 ms |
57588 KB |
Output is correct |
52 |
Correct |
1500 ms |
57576 KB |
Output is correct |
53 |
Correct |
1115 ms |
57704 KB |
Output is correct |
54 |
Correct |
1138 ms |
57704 KB |
Output is correct |
55 |
Correct |
1105 ms |
57728 KB |
Output is correct |
56 |
Correct |
171 ms |
1456 KB |
Output is correct |
57 |
Correct |
398 ms |
1584 KB |
Output is correct |
58 |
Correct |
673 ms |
2232 KB |
Output is correct |
59 |
Correct |
1711 ms |
49832 KB |
Output is correct |
60 |
Correct |
2380 ms |
50032 KB |
Output is correct |
61 |
Correct |
1494 ms |
66676 KB |
Output is correct |
62 |
Correct |
1313 ms |
70376 KB |
Output is correct |
63 |
Correct |
2100 ms |
69120 KB |
Output is correct |
64 |
Correct |
1687 ms |
67192 KB |
Output is correct |
65 |
Correct |
1507 ms |
66680 KB |
Output is correct |
66 |
Correct |
1822 ms |
66720 KB |
Output is correct |
67 |
Correct |
1691 ms |
70964 KB |
Output is correct |
68 |
Correct |
1375 ms |
80884 KB |
Output is correct |
69 |
Correct |
2093 ms |
89972 KB |
Output is correct |