#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 1e6 + 5, inf = 1e9;
int r[N], c[N],all;
int n,m;
vector <vector <int> > a; // map ?
struct nod {
int mnf, mns, cnt;
};
nod tree[4 * N];
int lazy[2][4 * N];
nod merge(nod a, nod b) {
if (a.mnf != b.mnf) {
return (a.mnf < b.mnf ? a : b);
}
if (a.mns != b.mns) {
return (a.mns < b.mns ? a : b);
}
return {a.mnf, a.mns, a.cnt + b.cnt};
}
void build(int node, int le, int ri) {
if (le == ri) {
tree[node] = {0, 0, 1};
return ;
}
int mid = (le + ri) / 2;
build(2 * node, le, mid);
build(2 * node + 1, mid + 1, ri);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
void push(int node, int le, int ri) {
if (!lazy[0][node] && !lazy[1][node]) return ;
tree[node].mnf += lazy[0][node];
tree[node].mns += lazy[1][node];
if (le != ri) {
for (int ty = 0; ty < 2; ty++) {
lazy[ty][2 * node] += lazy[ty][node];
lazy[ty][2 * node + 1] += lazy[ty][node];
}
}
lazy[0][node] = lazy[1][node] = 0;
}
void update(int node, int le, int ri, int start, int end, int val, int ty) {
push(node, le, ri);
if (le > end || ri < start) return ;
if (le >= start && ri <= end) {
lazy[ty][node] = val;
push(node, le, ri);
return ;
}
int mid = (le + ri) >> 1;
update(2 * node, le, mid,start, end, val, ty);
update(2 * node + 1, mid + 1, ri, start, end, val, ty);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
void upd(int l, int r, int vl, int ty) {
update(1, 1, all, l, r, vl, ty);
}
void add(int i, int j, int vl) {
vector <int> vec;
vec.pb(a[i][j]); vec.pb(a[i + 1][j]); vec.pb(a[i][j + 1]); vec.pb(a[i + 1][j + 1]);
sort(vec.begin(), vec.end());
if (vec[0] < vec[1]) upd(vec[0], vec[1] - 1, vl, 0);
if (vec[2] < vec[3]) upd(vec[2], vec[3] - 1, vl, 1);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n = H; m = W;
a = vector < vector <int> > (n + 5, vector <int> (m + 5, 0));
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++) {
a[i][j] = n * m + 1;
}
}
all = n * m;
for (int i = 0; i < n * m; i++) {
r[i + 1] = R[i] + 1; c[i + 1] = C[i] + 1;
a[r[i + 1]][c[i + 1]] = i + 1;
}
build(1, 1, all);
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// {i, j} {i + 1, j} {i, j + 1} {i + 1, j + 1}
add(i, j, 1);
}
}
}
int swap_seats(int x, int y) {
// {r[x], c[x]} --- >
x++; y++;
for (int ii = 0; ii < 2; ii++) {
int pos = (ii == 0 ? x : y);
for (int i = r[pos] - 1; i <= r[pos]; i++) {
for (int j = c[pos] - 1; j <= c[pos]; j++) {
add(i, j, -1);
}
}
}
a[r[x]][c[x]] = y;
a[r[y]][c[y]] = x;
swap(r[x], r[y]); swap(c[x], c[y]);
for (int ii = 0; ii < 2; ii++) {
int pos = (ii == 0 ? x : y);
for (int i = r[pos] - 1; i <= r[pos]; i++) {
for (int j = c[pos] - 1; j <= c[pos]; j++) {
add(i, j, 1);
}
}
}
if (tree[1].mnf == 4 && tree[1].mns == 0) {
return tree[1].cnt;
} else return 0;
}
Compilation message
seats.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
468 KB |
Output is correct |
2 |
Correct |
27 ms |
396 KB |
Output is correct |
3 |
Correct |
41 ms |
416 KB |
Output is correct |
4 |
Correct |
25 ms |
340 KB |
Output is correct |
5 |
Correct |
22 ms |
548 KB |
Output is correct |
6 |
Correct |
35 ms |
400 KB |
Output is correct |
7 |
Correct |
38 ms |
432 KB |
Output is correct |
8 |
Correct |
34 ms |
340 KB |
Output is correct |
9 |
Correct |
34 ms |
340 KB |
Output is correct |
10 |
Correct |
38 ms |
400 KB |
Output is correct |
11 |
Correct |
35 ms |
416 KB |
Output is correct |
12 |
Correct |
22 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
468 KB |
Output is correct |
2 |
Correct |
27 ms |
396 KB |
Output is correct |
3 |
Correct |
41 ms |
416 KB |
Output is correct |
4 |
Correct |
25 ms |
340 KB |
Output is correct |
5 |
Correct |
22 ms |
548 KB |
Output is correct |
6 |
Correct |
35 ms |
400 KB |
Output is correct |
7 |
Correct |
38 ms |
432 KB |
Output is correct |
8 |
Correct |
34 ms |
340 KB |
Output is correct |
9 |
Correct |
34 ms |
340 KB |
Output is correct |
10 |
Correct |
38 ms |
400 KB |
Output is correct |
11 |
Correct |
35 ms |
416 KB |
Output is correct |
12 |
Correct |
22 ms |
468 KB |
Output is correct |
13 |
Correct |
90 ms |
1280 KB |
Output is correct |
14 |
Correct |
103 ms |
1236 KB |
Output is correct |
15 |
Correct |
59 ms |
1528 KB |
Output is correct |
16 |
Correct |
41 ms |
1748 KB |
Output is correct |
17 |
Correct |
72 ms |
1396 KB |
Output is correct |
18 |
Correct |
66 ms |
1308 KB |
Output is correct |
19 |
Correct |
65 ms |
1344 KB |
Output is correct |
20 |
Correct |
55 ms |
1612 KB |
Output is correct |
21 |
Correct |
42 ms |
1520 KB |
Output is correct |
22 |
Correct |
42 ms |
1748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2532 ms |
69000 KB |
Output is correct |
2 |
Correct |
1208 ms |
69240 KB |
Output is correct |
3 |
Correct |
1110 ms |
68784 KB |
Output is correct |
4 |
Correct |
984 ms |
68872 KB |
Output is correct |
5 |
Correct |
1033 ms |
68792 KB |
Output is correct |
6 |
Correct |
957 ms |
68816 KB |
Output is correct |
7 |
Correct |
1029 ms |
68808 KB |
Output is correct |
8 |
Correct |
1064 ms |
68860 KB |
Output is correct |
9 |
Correct |
1079 ms |
68828 KB |
Output is correct |
10 |
Correct |
1054 ms |
68872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
83 ms |
1292 KB |
Output is correct |
2 |
Correct |
179 ms |
7996 KB |
Output is correct |
3 |
Correct |
993 ms |
68840 KB |
Output is correct |
4 |
Correct |
2441 ms |
68872 KB |
Output is correct |
5 |
Correct |
956 ms |
88372 KB |
Output is correct |
6 |
Correct |
2267 ms |
119680 KB |
Output is correct |
7 |
Correct |
985 ms |
75348 KB |
Output is correct |
8 |
Correct |
1211 ms |
69032 KB |
Output is correct |
9 |
Correct |
1046 ms |
69340 KB |
Output is correct |
10 |
Correct |
1075 ms |
75036 KB |
Output is correct |
11 |
Correct |
1006 ms |
98124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
106 ms |
1352 KB |
Output is correct |
2 |
Correct |
149 ms |
1304 KB |
Output is correct |
3 |
Correct |
221 ms |
1300 KB |
Output is correct |
4 |
Correct |
278 ms |
1352 KB |
Output is correct |
5 |
Correct |
463 ms |
2520 KB |
Output is correct |
6 |
Correct |
1540 ms |
88632 KB |
Output is correct |
7 |
Correct |
1857 ms |
88700 KB |
Output is correct |
8 |
Correct |
1528 ms |
88688 KB |
Output is correct |
9 |
Correct |
3220 ms |
88736 KB |
Output is correct |
10 |
Correct |
1482 ms |
88720 KB |
Output is correct |
11 |
Correct |
1461 ms |
88712 KB |
Output is correct |
12 |
Correct |
1397 ms |
88732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
468 KB |
Output is correct |
2 |
Correct |
27 ms |
396 KB |
Output is correct |
3 |
Correct |
41 ms |
416 KB |
Output is correct |
4 |
Correct |
25 ms |
340 KB |
Output is correct |
5 |
Correct |
22 ms |
548 KB |
Output is correct |
6 |
Correct |
35 ms |
400 KB |
Output is correct |
7 |
Correct |
38 ms |
432 KB |
Output is correct |
8 |
Correct |
34 ms |
340 KB |
Output is correct |
9 |
Correct |
34 ms |
340 KB |
Output is correct |
10 |
Correct |
38 ms |
400 KB |
Output is correct |
11 |
Correct |
35 ms |
416 KB |
Output is correct |
12 |
Correct |
22 ms |
468 KB |
Output is correct |
13 |
Correct |
90 ms |
1280 KB |
Output is correct |
14 |
Correct |
103 ms |
1236 KB |
Output is correct |
15 |
Correct |
59 ms |
1528 KB |
Output is correct |
16 |
Correct |
41 ms |
1748 KB |
Output is correct |
17 |
Correct |
72 ms |
1396 KB |
Output is correct |
18 |
Correct |
66 ms |
1308 KB |
Output is correct |
19 |
Correct |
65 ms |
1344 KB |
Output is correct |
20 |
Correct |
55 ms |
1612 KB |
Output is correct |
21 |
Correct |
42 ms |
1520 KB |
Output is correct |
22 |
Correct |
42 ms |
1748 KB |
Output is correct |
23 |
Correct |
2532 ms |
69000 KB |
Output is correct |
24 |
Correct |
1208 ms |
69240 KB |
Output is correct |
25 |
Correct |
1110 ms |
68784 KB |
Output is correct |
26 |
Correct |
984 ms |
68872 KB |
Output is correct |
27 |
Correct |
1033 ms |
68792 KB |
Output is correct |
28 |
Correct |
957 ms |
68816 KB |
Output is correct |
29 |
Correct |
1029 ms |
68808 KB |
Output is correct |
30 |
Correct |
1064 ms |
68860 KB |
Output is correct |
31 |
Correct |
1079 ms |
68828 KB |
Output is correct |
32 |
Correct |
1054 ms |
68872 KB |
Output is correct |
33 |
Correct |
83 ms |
1292 KB |
Output is correct |
34 |
Correct |
179 ms |
7996 KB |
Output is correct |
35 |
Correct |
993 ms |
68840 KB |
Output is correct |
36 |
Correct |
2441 ms |
68872 KB |
Output is correct |
37 |
Correct |
956 ms |
88372 KB |
Output is correct |
38 |
Correct |
2267 ms |
119680 KB |
Output is correct |
39 |
Correct |
985 ms |
75348 KB |
Output is correct |
40 |
Correct |
1211 ms |
69032 KB |
Output is correct |
41 |
Correct |
1046 ms |
69340 KB |
Output is correct |
42 |
Correct |
1075 ms |
75036 KB |
Output is correct |
43 |
Correct |
1006 ms |
98124 KB |
Output is correct |
44 |
Correct |
106 ms |
1352 KB |
Output is correct |
45 |
Correct |
149 ms |
1304 KB |
Output is correct |
46 |
Correct |
221 ms |
1300 KB |
Output is correct |
47 |
Correct |
278 ms |
1352 KB |
Output is correct |
48 |
Correct |
463 ms |
2520 KB |
Output is correct |
49 |
Correct |
1540 ms |
88632 KB |
Output is correct |
50 |
Correct |
1857 ms |
88700 KB |
Output is correct |
51 |
Correct |
1528 ms |
88688 KB |
Output is correct |
52 |
Correct |
3220 ms |
88736 KB |
Output is correct |
53 |
Correct |
1482 ms |
88720 KB |
Output is correct |
54 |
Correct |
1461 ms |
88712 KB |
Output is correct |
55 |
Correct |
1397 ms |
88732 KB |
Output is correct |
56 |
Correct |
191 ms |
1324 KB |
Output is correct |
57 |
Correct |
409 ms |
1364 KB |
Output is correct |
58 |
Correct |
632 ms |
2272 KB |
Output is correct |
59 |
Correct |
2037 ms |
69176 KB |
Output is correct |
60 |
Correct |
3896 ms |
69228 KB |
Output is correct |
61 |
Correct |
1867 ms |
85836 KB |
Output is correct |
62 |
Correct |
1578 ms |
95564 KB |
Output is correct |
63 |
Correct |
3943 ms |
92280 KB |
Output is correct |
64 |
Correct |
2354 ms |
87756 KB |
Output is correct |
65 |
Correct |
2049 ms |
86084 KB |
Output is correct |
66 |
Correct |
2141 ms |
86212 KB |
Output is correct |
67 |
Correct |
2280 ms |
92008 KB |
Output is correct |
68 |
Correct |
1693 ms |
105316 KB |
Output is correct |
69 |
Correct |
3438 ms |
117064 KB |
Output is correct |