# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
75005 |
2018-09-08T03:10:46 Z |
ainta |
Seats (IOI18_seats) |
C++17 |
|
2594 ms |
103740 KB |
#include "seats.h"
#include <algorithm>
#include <vector>
#define N_ 1010000
#define SZ 1048576
#define pii pair<int,int>
using namespace std;
vector<vector<int> >w;
int H, W, n, dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
struct point {
int x, y;
}P[N_];
int Get(int x, int y) {
if (x < 0 || x >= H || y < 0 || y >= W)return n;
return w[x][y];
}
struct Seg {
int Mn[SZ + SZ];
int C[SZ + SZ];
int K[SZ + SZ];
void UDT(int nd) {
int mm = min(Mn[nd * 2], Mn[nd * 2 + 1]);
Mn[nd] = mm;
C[nd] = 0;
if (mm == Mn[nd * 2])C[nd] += C[nd * 2];
if (mm == Mn[nd * 2 + 1])C[nd] += C[nd * 2 + 1];
}
void init(int nd, int b, int e) {
if (b == e) {
C[nd] = 1;
return;
}
int m = (b + e) >> 1;
init(nd * 2, b, m);
init(nd * 2 + 1, m + 1, e);
UDT(nd);
}
void Add2(int nd, int x) {
Mn[nd] += x;
K[nd] += x;
}
void Spread(int nd) {
Add2(nd * 2, K[nd]);
Add2(nd * 2 + 1, K[nd]);
K[nd] = 0;
}
void Add(int nd, int b, int e, int s, int l, int x) {
if (b == s && e == l) {
Add2(nd, x);
return;
}
Spread(nd);
int m = (b + e) >> 1;
if (s <= m)Add(nd * 2, b, m, s, min(m, l), x);
if (l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, x);
UDT(nd);
}
}T;
void Put(int x, int y, int ck) {
int i, j;
if (x < 0 || x >= H || y < 0 || y >= W)return;
int t = min(Get(x - 1, y), Get(x, y - 1));
if (w[x][y] < t)T.Add(1, 0, n - 1, w[x][y], t - 1, ck);
int TP[4];
for (i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
TP[i] = Get(tx, ty);
}
sort(TP, TP + 4);
if (TP[1] < w[x][y]) T.Add(1, 0, n - 1, TP[1], w[x][y] - 1, ck);
}
void give_initial_chart(int HH, int WW, std::vector<int> R, std::vector<int> C) {
int i, j;
H = HH;
W = WW;
n = H*W;
w.resize(H);
T.init(1, 0, n - 1);
for (i = 0; i < H; i++)w[i].resize(W);
for (i = 0; i < n; i++) {
P[i] = { R[i],C[i] };
w[R[i]][C[i]] = i;
}
for (i = 0; i < H; i++)for (j = 0; j < W; j++) {
Put(i, j, 1);
}
}
int swap_seats(int a, int b) {
vector<pii>TP;
TP.push_back({ P[a].x,P[a].y });
TP.push_back({ P[b].x,P[b].y });
for (int i = 0; i < 4; i++) {
TP.push_back({ P[a].x + dx[i], P[a].y + dy[i] });
TP.push_back({ P[b].x + dx[i], P[b].y + dy[i] });
}
sort(TP.begin(), TP.end());
TP.resize(unique(TP.begin(), TP.end()) - TP.begin());
for (auto &t : TP) {
Put(t.first, t.second, -1);
}
swap(w[P[a].x][P[a].y], w[P[b].x][P[b].y]);
swap(P[a], P[b]);
for (auto &t : TP) {
Put(t.first, t.second, 1);
}
return T.C[1];
}
Compilation message
seats.cpp: In function 'void Put(int, int, int)':
seats.cpp:64:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
504 KB |
Output is correct |
2 |
Correct |
19 ms |
508 KB |
Output is correct |
3 |
Correct |
29 ms |
672 KB |
Output is correct |
4 |
Correct |
20 ms |
672 KB |
Output is correct |
5 |
Correct |
12 ms |
672 KB |
Output is correct |
6 |
Correct |
25 ms |
672 KB |
Output is correct |
7 |
Correct |
27 ms |
672 KB |
Output is correct |
8 |
Correct |
25 ms |
784 KB |
Output is correct |
9 |
Correct |
22 ms |
784 KB |
Output is correct |
10 |
Correct |
27 ms |
788 KB |
Output is correct |
11 |
Correct |
32 ms |
800 KB |
Output is correct |
12 |
Correct |
21 ms |
800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
504 KB |
Output is correct |
2 |
Correct |
19 ms |
508 KB |
Output is correct |
3 |
Correct |
29 ms |
672 KB |
Output is correct |
4 |
Correct |
20 ms |
672 KB |
Output is correct |
5 |
Correct |
12 ms |
672 KB |
Output is correct |
6 |
Correct |
25 ms |
672 KB |
Output is correct |
7 |
Correct |
27 ms |
672 KB |
Output is correct |
8 |
Correct |
25 ms |
784 KB |
Output is correct |
9 |
Correct |
22 ms |
784 KB |
Output is correct |
10 |
Correct |
27 ms |
788 KB |
Output is correct |
11 |
Correct |
32 ms |
800 KB |
Output is correct |
12 |
Correct |
21 ms |
800 KB |
Output is correct |
13 |
Correct |
58 ms |
1388 KB |
Output is correct |
14 |
Correct |
67 ms |
1388 KB |
Output is correct |
15 |
Correct |
52 ms |
1388 KB |
Output is correct |
16 |
Correct |
23 ms |
1888 KB |
Output is correct |
17 |
Correct |
56 ms |
1888 KB |
Output is correct |
18 |
Correct |
45 ms |
1888 KB |
Output is correct |
19 |
Correct |
43 ms |
1888 KB |
Output is correct |
20 |
Correct |
46 ms |
1888 KB |
Output is correct |
21 |
Correct |
39 ms |
1888 KB |
Output is correct |
22 |
Correct |
34 ms |
1888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1689 ms |
52684 KB |
Output is correct |
2 |
Correct |
807 ms |
52684 KB |
Output is correct |
3 |
Correct |
987 ms |
52924 KB |
Output is correct |
4 |
Correct |
610 ms |
52924 KB |
Output is correct |
5 |
Correct |
677 ms |
52924 KB |
Output is correct |
6 |
Correct |
1000 ms |
52932 KB |
Output is correct |
7 |
Correct |
928 ms |
52932 KB |
Output is correct |
8 |
Correct |
884 ms |
52932 KB |
Output is correct |
9 |
Correct |
864 ms |
52932 KB |
Output is correct |
10 |
Correct |
786 ms |
52932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
52932 KB |
Output is correct |
2 |
Correct |
123 ms |
52932 KB |
Output is correct |
3 |
Correct |
809 ms |
52932 KB |
Output is correct |
4 |
Correct |
1531 ms |
52932 KB |
Output is correct |
5 |
Correct |
650 ms |
52932 KB |
Output is correct |
6 |
Correct |
1562 ms |
103740 KB |
Output is correct |
7 |
Correct |
654 ms |
103740 KB |
Output is correct |
8 |
Correct |
1004 ms |
103740 KB |
Output is correct |
9 |
Correct |
911 ms |
103740 KB |
Output is correct |
10 |
Correct |
755 ms |
103740 KB |
Output is correct |
11 |
Correct |
706 ms |
103740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
103740 KB |
Output is correct |
2 |
Correct |
119 ms |
103740 KB |
Output is correct |
3 |
Correct |
172 ms |
103740 KB |
Output is correct |
4 |
Correct |
208 ms |
103740 KB |
Output is correct |
5 |
Correct |
337 ms |
103740 KB |
Output is correct |
6 |
Correct |
1111 ms |
103740 KB |
Output is correct |
7 |
Correct |
1237 ms |
103740 KB |
Output is correct |
8 |
Correct |
1077 ms |
103740 KB |
Output is correct |
9 |
Correct |
1940 ms |
103740 KB |
Output is correct |
10 |
Correct |
1037 ms |
103740 KB |
Output is correct |
11 |
Correct |
1073 ms |
103740 KB |
Output is correct |
12 |
Correct |
681 ms |
103740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
504 KB |
Output is correct |
2 |
Correct |
19 ms |
508 KB |
Output is correct |
3 |
Correct |
29 ms |
672 KB |
Output is correct |
4 |
Correct |
20 ms |
672 KB |
Output is correct |
5 |
Correct |
12 ms |
672 KB |
Output is correct |
6 |
Correct |
25 ms |
672 KB |
Output is correct |
7 |
Correct |
27 ms |
672 KB |
Output is correct |
8 |
Correct |
25 ms |
784 KB |
Output is correct |
9 |
Correct |
22 ms |
784 KB |
Output is correct |
10 |
Correct |
27 ms |
788 KB |
Output is correct |
11 |
Correct |
32 ms |
800 KB |
Output is correct |
12 |
Correct |
21 ms |
800 KB |
Output is correct |
13 |
Correct |
58 ms |
1388 KB |
Output is correct |
14 |
Correct |
67 ms |
1388 KB |
Output is correct |
15 |
Correct |
52 ms |
1388 KB |
Output is correct |
16 |
Correct |
23 ms |
1888 KB |
Output is correct |
17 |
Correct |
56 ms |
1888 KB |
Output is correct |
18 |
Correct |
45 ms |
1888 KB |
Output is correct |
19 |
Correct |
43 ms |
1888 KB |
Output is correct |
20 |
Correct |
46 ms |
1888 KB |
Output is correct |
21 |
Correct |
39 ms |
1888 KB |
Output is correct |
22 |
Correct |
34 ms |
1888 KB |
Output is correct |
23 |
Correct |
1689 ms |
52684 KB |
Output is correct |
24 |
Correct |
807 ms |
52684 KB |
Output is correct |
25 |
Correct |
987 ms |
52924 KB |
Output is correct |
26 |
Correct |
610 ms |
52924 KB |
Output is correct |
27 |
Correct |
677 ms |
52924 KB |
Output is correct |
28 |
Correct |
1000 ms |
52932 KB |
Output is correct |
29 |
Correct |
928 ms |
52932 KB |
Output is correct |
30 |
Correct |
884 ms |
52932 KB |
Output is correct |
31 |
Correct |
864 ms |
52932 KB |
Output is correct |
32 |
Correct |
786 ms |
52932 KB |
Output is correct |
33 |
Correct |
58 ms |
52932 KB |
Output is correct |
34 |
Correct |
123 ms |
52932 KB |
Output is correct |
35 |
Correct |
809 ms |
52932 KB |
Output is correct |
36 |
Correct |
1531 ms |
52932 KB |
Output is correct |
37 |
Correct |
650 ms |
52932 KB |
Output is correct |
38 |
Correct |
1562 ms |
103740 KB |
Output is correct |
39 |
Correct |
654 ms |
103740 KB |
Output is correct |
40 |
Correct |
1004 ms |
103740 KB |
Output is correct |
41 |
Correct |
911 ms |
103740 KB |
Output is correct |
42 |
Correct |
755 ms |
103740 KB |
Output is correct |
43 |
Correct |
706 ms |
103740 KB |
Output is correct |
44 |
Correct |
75 ms |
103740 KB |
Output is correct |
45 |
Correct |
119 ms |
103740 KB |
Output is correct |
46 |
Correct |
172 ms |
103740 KB |
Output is correct |
47 |
Correct |
208 ms |
103740 KB |
Output is correct |
48 |
Correct |
337 ms |
103740 KB |
Output is correct |
49 |
Correct |
1111 ms |
103740 KB |
Output is correct |
50 |
Correct |
1237 ms |
103740 KB |
Output is correct |
51 |
Correct |
1077 ms |
103740 KB |
Output is correct |
52 |
Correct |
1940 ms |
103740 KB |
Output is correct |
53 |
Correct |
1037 ms |
103740 KB |
Output is correct |
54 |
Correct |
1073 ms |
103740 KB |
Output is correct |
55 |
Correct |
681 ms |
103740 KB |
Output is correct |
56 |
Correct |
146 ms |
103740 KB |
Output is correct |
57 |
Correct |
271 ms |
103740 KB |
Output is correct |
58 |
Correct |
390 ms |
103740 KB |
Output is correct |
59 |
Correct |
1762 ms |
103740 KB |
Output is correct |
60 |
Correct |
2594 ms |
103740 KB |
Output is correct |
61 |
Correct |
1128 ms |
103740 KB |
Output is correct |
62 |
Correct |
1105 ms |
103740 KB |
Output is correct |
63 |
Correct |
2395 ms |
103740 KB |
Output is correct |
64 |
Correct |
1626 ms |
103740 KB |
Output is correct |
65 |
Correct |
1355 ms |
103740 KB |
Output is correct |
66 |
Correct |
1785 ms |
103740 KB |
Output is correct |
67 |
Correct |
1349 ms |
103740 KB |
Output is correct |
68 |
Correct |
1149 ms |
103740 KB |
Output is correct |
69 |
Correct |
2432 ms |
103740 KB |
Output is correct |