/// simba :(
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int N, M, K;
vector<int> X, Y;
vector< vector<int> > A;
class SegmentTree
{
public:
int N;
int sti, dri, val;
vector<int> aint, add, cnt;
void B(int nod, int st, int dr)
{
aint[nod] = add[nod] = 0, cnt[nod] = dr - st + 1;
if(st == dr) return;
B(nod * 2, st, st + (dr - st) / 2);
B(nod * 2 + 1, st + (dr - st) / 2 + 1, dr);
}
void U(int nod, int st, int dr)
{
if(sti <= st && dr <= dri)
{
aint[nod] += val;
add[nod] += val;
return;
}
int mij = st + (dr - st) / 2;
if(add[nod])
{
aint[nod * 2] += add[nod];
aint[nod * 2 + 1] += add[nod];
add[nod * 2] += add[nod];
add[nod * 2 + 1] += add[nod];
add[nod] = 0;
}
if(sti <= mij) U(nod * 2, st, mij);
if(mij < dri) U(nod * 2 + 1, mij + 1, dr);
aint[nod] = min(aint[nod * 2], aint[nod * 2 + 1]);
cnt[nod] = 0;
if(aint[nod] == aint[nod * 2]) cnt[nod] += cnt[nod * 2];
if(aint[nod] == aint[nod * 2 + 1]) cnt[nod] += cnt[nod * 2 + 1];
}
void build(int _N)
{
N = _N;
aint.resize(4 * N), add.resize(4 * N), cnt.resize(4 * N);
B(1, 0, N - 1);
}
void update(int st, int dr, int v)
{
if(st > dr) return;
sti = st, dri = dr, val = v;
U(1, 0, N - 1);
}
int query()
{
return cnt[1];
}
}aint;
int a(int x, int y)
{
if(x < 0 || y < 0 || x >= N || y >= M) return K;
return A[x][y];
}
void makeBlack(int x, int y, int add)
{
if(x < 0 || y < 0 || x >= N || y >= M) return;
int t = min(a(x - 1, y), a(x, y - 1));
aint.update(a(x, y), t - 1, add);
}
void makeWhite(int x, int y, int add)
{
if(x < 0 || y < 0 || x >= N || y >= M) return;
vector<int> t;
t.push_back(a(x - 1, y));
t.push_back(a(x + 1, y));
t.push_back(a(x, y - 1));
t.push_back(a(x, y + 1));
sort(t.begin(), t.end());
int tt = t[1];
aint.update(tt, a(x, y) - 1, add);
}
void solveCell(int x, int y, int add)
{
makeBlack(x, y, add);
makeBlack(x + 1, y, add);
makeBlack(x, y + 1, add);
makeWhite(x, y, add);
makeWhite(x - 1, y, add);
makeWhite(x + 1, y, add);
makeWhite(x, y - 1, add);
makeWhite(x, y + 1, add);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
N = H, M = W;
K = N * M;
X = R, Y = C;
A.resize(N);
for(int i = 0; i < N; i++) A[i].resize(M);
for(int i = 0; i < K; i++)
A[ X[i] ][ Y[i] ] = i;
aint.build(K);
for(int i = 0; i < K; i++)
{
makeBlack(X[i], Y[i], 1);
makeWhite(X[i], Y[i], 1);
}
}
const int cx[] = {0, -1, 1, 0, 0};
const int cy[] = {0, 0, 0, -1, 1};
int swap_seats(int a, int b)
{
vector<pii> cells;
for(int i = 0; i < 5; i++) cells.push_back({X[a] + cx[i], Y[a] + cy[i]});
for(int i = 0; i < 5; i++) cells.push_back({X[b] + cx[i], Y[b] + cy[i]});
sort(cells.begin(), cells.end());
cells.resize(unique(cells.begin(), cells.end()) - cells.begin());
for(auto p: cells)
{
makeBlack(p.first, p.second, -1);
makeWhite(p.first, p.second, -1);
}
swap(X[a], X[b]);
swap(Y[a], Y[b]);
A[ X[a] ][ Y[a] ] = a;
A[ X[b] ][ Y[b] ] = b;
for(auto p: cells)
{
makeBlack(p.first, p.second, 1);
makeWhite(p.first, p.second, 1);
}
return aint.query();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
376 KB |
Output is correct |
2 |
Correct |
34 ms |
508 KB |
Output is correct |
3 |
Correct |
46 ms |
476 KB |
Output is correct |
4 |
Correct |
29 ms |
504 KB |
Output is correct |
5 |
Correct |
22 ms |
504 KB |
Output is correct |
6 |
Correct |
41 ms |
496 KB |
Output is correct |
7 |
Correct |
44 ms |
552 KB |
Output is correct |
8 |
Correct |
40 ms |
504 KB |
Output is correct |
9 |
Correct |
38 ms |
512 KB |
Output is correct |
10 |
Correct |
44 ms |
504 KB |
Output is correct |
11 |
Correct |
40 ms |
504 KB |
Output is correct |
12 |
Correct |
28 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
376 KB |
Output is correct |
2 |
Correct |
34 ms |
508 KB |
Output is correct |
3 |
Correct |
46 ms |
476 KB |
Output is correct |
4 |
Correct |
29 ms |
504 KB |
Output is correct |
5 |
Correct |
22 ms |
504 KB |
Output is correct |
6 |
Correct |
41 ms |
496 KB |
Output is correct |
7 |
Correct |
44 ms |
552 KB |
Output is correct |
8 |
Correct |
40 ms |
504 KB |
Output is correct |
9 |
Correct |
38 ms |
512 KB |
Output is correct |
10 |
Correct |
44 ms |
504 KB |
Output is correct |
11 |
Correct |
40 ms |
504 KB |
Output is correct |
12 |
Correct |
28 ms |
632 KB |
Output is correct |
13 |
Correct |
79 ms |
1276 KB |
Output is correct |
14 |
Correct |
92 ms |
1400 KB |
Output is correct |
15 |
Correct |
61 ms |
1400 KB |
Output is correct |
16 |
Correct |
34 ms |
1912 KB |
Output is correct |
17 |
Correct |
73 ms |
1372 KB |
Output is correct |
18 |
Correct |
67 ms |
1272 KB |
Output is correct |
19 |
Correct |
61 ms |
1500 KB |
Output is correct |
20 |
Correct |
57 ms |
1532 KB |
Output is correct |
21 |
Correct |
46 ms |
1400 KB |
Output is correct |
22 |
Correct |
45 ms |
1884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2152 ms |
74872 KB |
Output is correct |
2 |
Correct |
968 ms |
74892 KB |
Output is correct |
3 |
Correct |
1079 ms |
74972 KB |
Output is correct |
4 |
Correct |
832 ms |
74756 KB |
Output is correct |
5 |
Correct |
972 ms |
74768 KB |
Output is correct |
6 |
Correct |
1354 ms |
74844 KB |
Output is correct |
7 |
Correct |
1189 ms |
74756 KB |
Output is correct |
8 |
Correct |
1002 ms |
75000 KB |
Output is correct |
9 |
Correct |
1030 ms |
74920 KB |
Output is correct |
10 |
Correct |
900 ms |
74940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
1272 KB |
Output is correct |
2 |
Correct |
160 ms |
7120 KB |
Output is correct |
3 |
Correct |
1046 ms |
90800 KB |
Output is correct |
4 |
Correct |
2133 ms |
90872 KB |
Output is correct |
5 |
Correct |
924 ms |
90744 KB |
Output is correct |
6 |
Correct |
2158 ms |
141664 KB |
Output is correct |
7 |
Correct |
950 ms |
90752 KB |
Output is correct |
8 |
Correct |
1194 ms |
90844 KB |
Output is correct |
9 |
Correct |
1010 ms |
91000 KB |
Output is correct |
10 |
Correct |
994 ms |
93944 KB |
Output is correct |
11 |
Correct |
934 ms |
114228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
117 ms |
1396 KB |
Output is correct |
2 |
Correct |
197 ms |
2028 KB |
Output is correct |
3 |
Correct |
260 ms |
2132 KB |
Output is correct |
4 |
Correct |
294 ms |
2168 KB |
Output is correct |
5 |
Correct |
467 ms |
2804 KB |
Output is correct |
6 |
Correct |
1590 ms |
91768 KB |
Output is correct |
7 |
Correct |
1720 ms |
91908 KB |
Output is correct |
8 |
Correct |
1482 ms |
91772 KB |
Output is correct |
9 |
Correct |
2465 ms |
91740 KB |
Output is correct |
10 |
Correct |
1396 ms |
91768 KB |
Output is correct |
11 |
Correct |
1420 ms |
91672 KB |
Output is correct |
12 |
Correct |
899 ms |
91652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
376 KB |
Output is correct |
2 |
Correct |
34 ms |
508 KB |
Output is correct |
3 |
Correct |
46 ms |
476 KB |
Output is correct |
4 |
Correct |
29 ms |
504 KB |
Output is correct |
5 |
Correct |
22 ms |
504 KB |
Output is correct |
6 |
Correct |
41 ms |
496 KB |
Output is correct |
7 |
Correct |
44 ms |
552 KB |
Output is correct |
8 |
Correct |
40 ms |
504 KB |
Output is correct |
9 |
Correct |
38 ms |
512 KB |
Output is correct |
10 |
Correct |
44 ms |
504 KB |
Output is correct |
11 |
Correct |
40 ms |
504 KB |
Output is correct |
12 |
Correct |
28 ms |
632 KB |
Output is correct |
13 |
Correct |
79 ms |
1276 KB |
Output is correct |
14 |
Correct |
92 ms |
1400 KB |
Output is correct |
15 |
Correct |
61 ms |
1400 KB |
Output is correct |
16 |
Correct |
34 ms |
1912 KB |
Output is correct |
17 |
Correct |
73 ms |
1372 KB |
Output is correct |
18 |
Correct |
67 ms |
1272 KB |
Output is correct |
19 |
Correct |
61 ms |
1500 KB |
Output is correct |
20 |
Correct |
57 ms |
1532 KB |
Output is correct |
21 |
Correct |
46 ms |
1400 KB |
Output is correct |
22 |
Correct |
45 ms |
1884 KB |
Output is correct |
23 |
Correct |
2152 ms |
74872 KB |
Output is correct |
24 |
Correct |
968 ms |
74892 KB |
Output is correct |
25 |
Correct |
1079 ms |
74972 KB |
Output is correct |
26 |
Correct |
832 ms |
74756 KB |
Output is correct |
27 |
Correct |
972 ms |
74768 KB |
Output is correct |
28 |
Correct |
1354 ms |
74844 KB |
Output is correct |
29 |
Correct |
1189 ms |
74756 KB |
Output is correct |
30 |
Correct |
1002 ms |
75000 KB |
Output is correct |
31 |
Correct |
1030 ms |
74920 KB |
Output is correct |
32 |
Correct |
900 ms |
74940 KB |
Output is correct |
33 |
Correct |
82 ms |
1272 KB |
Output is correct |
34 |
Correct |
160 ms |
7120 KB |
Output is correct |
35 |
Correct |
1046 ms |
90800 KB |
Output is correct |
36 |
Correct |
2133 ms |
90872 KB |
Output is correct |
37 |
Correct |
924 ms |
90744 KB |
Output is correct |
38 |
Correct |
2158 ms |
141664 KB |
Output is correct |
39 |
Correct |
950 ms |
90752 KB |
Output is correct |
40 |
Correct |
1194 ms |
90844 KB |
Output is correct |
41 |
Correct |
1010 ms |
91000 KB |
Output is correct |
42 |
Correct |
994 ms |
93944 KB |
Output is correct |
43 |
Correct |
934 ms |
114228 KB |
Output is correct |
44 |
Correct |
117 ms |
1396 KB |
Output is correct |
45 |
Correct |
197 ms |
2028 KB |
Output is correct |
46 |
Correct |
260 ms |
2132 KB |
Output is correct |
47 |
Correct |
294 ms |
2168 KB |
Output is correct |
48 |
Correct |
467 ms |
2804 KB |
Output is correct |
49 |
Correct |
1590 ms |
91768 KB |
Output is correct |
50 |
Correct |
1720 ms |
91908 KB |
Output is correct |
51 |
Correct |
1482 ms |
91772 KB |
Output is correct |
52 |
Correct |
2465 ms |
91740 KB |
Output is correct |
53 |
Correct |
1396 ms |
91768 KB |
Output is correct |
54 |
Correct |
1420 ms |
91672 KB |
Output is correct |
55 |
Correct |
899 ms |
91652 KB |
Output is correct |
56 |
Correct |
245 ms |
2064 KB |
Output is correct |
57 |
Correct |
451 ms |
2200 KB |
Output is correct |
58 |
Correct |
576 ms |
2932 KB |
Output is correct |
59 |
Correct |
2316 ms |
91860 KB |
Output is correct |
60 |
Correct |
3434 ms |
91768 KB |
Output is correct |
61 |
Correct |
1484 ms |
91768 KB |
Output is correct |
62 |
Correct |
1550 ms |
91772 KB |
Output is correct |
63 |
Correct |
3164 ms |
91756 KB |
Output is correct |
64 |
Correct |
2170 ms |
91772 KB |
Output is correct |
65 |
Correct |
1737 ms |
91688 KB |
Output is correct |
66 |
Correct |
2210 ms |
92148 KB |
Output is correct |
67 |
Correct |
1885 ms |
94840 KB |
Output is correct |
68 |
Correct |
1560 ms |
106100 KB |
Output is correct |
69 |
Correct |
3253 ms |
115320 KB |
Output is correct |