# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
76357 |
2018-09-13T02:11:17 Z |
kriii |
Seats (IOI18_seats) |
C++17 |
|
1482 ms |
54528 KB |
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int Z = 1<<20;
struct node{
node()
{
sum = min = 0; cnt = 1;
}
node(int v)
{
sum = min = v; cnt = 1;
}
int sum, min, cnt;
node operator *(const node &t) const{
node res;
res.sum = sum + t.sum;
if (min < sum + t.min) res.min = min;
else res.min = sum + t.min;
res.cnt = 0;
if (res.min == min) res.cnt += cnt;
if (res.min == sum + t.min) res.cnt += t.cnt;
return res;
}
void add(int p)
{
sum += p;
min += p;
}
} IT[Z*2];
int N,A[1001001]; bool chk[1001001]; int H,W; vector<int> R,C;
void upd(int x)
{
x /= 2;
while (x){
IT[x] = IT[x*2] * IT[x*2+1];
x /= 2;
}
}
set<int> ups;
void add(int i, int p, bool up = true)
{
if (p > 0){
if (chk[i]) return;
chk[i] = 1;
}
else{
if (!chk[i]) return;
chk[i] = 0;
}
int x = R[i], y = C[i];
int dx[5] = {0,1,0,-1,0};
int dy[5] = {1,0,-1,0,1};
for (int k=0;k<4;k++){
int u[2];
for (int d=0;d<2;d++){
int px = x + dx[k+d];
int py = y + dy[k+d];
if (px < 0 || px >= H || py < 0 || py >= W) u[d] = N;
else u[d] = A[px*W+py];
}
int s = N, e = 0;
if (i < u[0] && i < u[1]){
s = i + Z;
e = min(u[0],u[1]) + Z;
}
if (u[0] < i && u[1] < i){
s = max(u[0],u[1]) + Z;
e = i + Z;
}
if (s < e){
IT[s].add(+p);
IT[e].add(-p);
if (up){
ups.insert(s);
ups.insert(e);
}
}
}
}
void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_)
{
H = H_; W = W_; R = R_; C = C_; N = H * W;
for (int i=0;i<N;i++) A[R[i]*W+C[i]] = i;
IT[N+Z].add(10000);
for (int i=0;i<N;i++) add(i,1,false);
for (int i=Z-1;i>=1;i--) IT[i] = IT[i*2] * IT[i*2+1];
}
int swap_seats(int a, int b)
{
int dx[5] = {0,1,0,-1,0};
int dy[5] = {1,0,-1,0,0};
for (int i : {a,b}) for (int k=0;k<5;k++){
int x = R[i] + dx[k];
int y = C[i] + dy[k];
if (x < 0 || x >= H || y < 0 || y >= W) continue;
add(A[x*W+y],-1);
}
swap(R[a],R[b]);
swap(C[a],C[b]);
A[R[a]*W+C[a]] = a;
A[R[b]*W+C[b]] = b;
for (int i : {a,b}) for (int k=0;k<5;k++){
int x = R[i] + dx[k];
int y = C[i] + dy[k];
if (x < 0 || x >= H || y < 0 || y >= W) continue;
add(A[x*W+y],+1);
}
for (int x : ups) upd(x);
ups.clear();
return IT[1].min == 4 ? IT[1].cnt : 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
25080 KB |
Output is correct |
2 |
Correct |
65 ms |
25084 KB |
Output is correct |
3 |
Correct |
73 ms |
25176 KB |
Output is correct |
4 |
Correct |
49 ms |
25268 KB |
Output is correct |
5 |
Correct |
42 ms |
25356 KB |
Output is correct |
6 |
Correct |
68 ms |
25356 KB |
Output is correct |
7 |
Correct |
69 ms |
25356 KB |
Output is correct |
8 |
Correct |
74 ms |
25356 KB |
Output is correct |
9 |
Correct |
69 ms |
25356 KB |
Output is correct |
10 |
Correct |
88 ms |
25476 KB |
Output is correct |
11 |
Correct |
75 ms |
25476 KB |
Output is correct |
12 |
Correct |
43 ms |
25476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
25080 KB |
Output is correct |
2 |
Correct |
65 ms |
25084 KB |
Output is correct |
3 |
Correct |
73 ms |
25176 KB |
Output is correct |
4 |
Correct |
49 ms |
25268 KB |
Output is correct |
5 |
Correct |
42 ms |
25356 KB |
Output is correct |
6 |
Correct |
68 ms |
25356 KB |
Output is correct |
7 |
Correct |
69 ms |
25356 KB |
Output is correct |
8 |
Correct |
74 ms |
25356 KB |
Output is correct |
9 |
Correct |
69 ms |
25356 KB |
Output is correct |
10 |
Correct |
88 ms |
25476 KB |
Output is correct |
11 |
Correct |
75 ms |
25476 KB |
Output is correct |
12 |
Correct |
43 ms |
25476 KB |
Output is correct |
13 |
Correct |
82 ms |
25624 KB |
Output is correct |
14 |
Correct |
85 ms |
25624 KB |
Output is correct |
15 |
Correct |
54 ms |
25628 KB |
Output is correct |
16 |
Correct |
46 ms |
25672 KB |
Output is correct |
17 |
Correct |
71 ms |
25672 KB |
Output is correct |
18 |
Correct |
82 ms |
25672 KB |
Output is correct |
19 |
Correct |
85 ms |
25672 KB |
Output is correct |
20 |
Correct |
57 ms |
25672 KB |
Output is correct |
21 |
Correct |
46 ms |
25672 KB |
Output is correct |
22 |
Correct |
48 ms |
25672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
664 ms |
53792 KB |
Output is correct |
2 |
Correct |
486 ms |
53792 KB |
Output is correct |
3 |
Correct |
460 ms |
53792 KB |
Output is correct |
4 |
Correct |
455 ms |
53792 KB |
Output is correct |
5 |
Correct |
475 ms |
53792 KB |
Output is correct |
6 |
Correct |
441 ms |
53792 KB |
Output is correct |
7 |
Correct |
462 ms |
53792 KB |
Output is correct |
8 |
Correct |
458 ms |
53820 KB |
Output is correct |
9 |
Correct |
461 ms |
53820 KB |
Output is correct |
10 |
Correct |
465 ms |
53820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
53820 KB |
Output is correct |
2 |
Correct |
115 ms |
53820 KB |
Output is correct |
3 |
Correct |
459 ms |
53820 KB |
Output is correct |
4 |
Correct |
686 ms |
53820 KB |
Output is correct |
5 |
Correct |
407 ms |
53820 KB |
Output is correct |
6 |
Correct |
554 ms |
53820 KB |
Output is correct |
7 |
Correct |
447 ms |
53820 KB |
Output is correct |
8 |
Correct |
465 ms |
53872 KB |
Output is correct |
9 |
Correct |
510 ms |
53884 KB |
Output is correct |
10 |
Correct |
479 ms |
53952 KB |
Output is correct |
11 |
Correct |
433 ms |
53952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
105 ms |
53952 KB |
Output is correct |
2 |
Correct |
204 ms |
53952 KB |
Output is correct |
3 |
Correct |
189 ms |
53952 KB |
Output is correct |
4 |
Correct |
200 ms |
53952 KB |
Output is correct |
5 |
Correct |
240 ms |
53952 KB |
Output is correct |
6 |
Correct |
632 ms |
54228 KB |
Output is correct |
7 |
Correct |
689 ms |
54336 KB |
Output is correct |
8 |
Correct |
626 ms |
54336 KB |
Output is correct |
9 |
Correct |
929 ms |
54464 KB |
Output is correct |
10 |
Correct |
602 ms |
54464 KB |
Output is correct |
11 |
Correct |
599 ms |
54464 KB |
Output is correct |
12 |
Correct |
632 ms |
54464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
25080 KB |
Output is correct |
2 |
Correct |
65 ms |
25084 KB |
Output is correct |
3 |
Correct |
73 ms |
25176 KB |
Output is correct |
4 |
Correct |
49 ms |
25268 KB |
Output is correct |
5 |
Correct |
42 ms |
25356 KB |
Output is correct |
6 |
Correct |
68 ms |
25356 KB |
Output is correct |
7 |
Correct |
69 ms |
25356 KB |
Output is correct |
8 |
Correct |
74 ms |
25356 KB |
Output is correct |
9 |
Correct |
69 ms |
25356 KB |
Output is correct |
10 |
Correct |
88 ms |
25476 KB |
Output is correct |
11 |
Correct |
75 ms |
25476 KB |
Output is correct |
12 |
Correct |
43 ms |
25476 KB |
Output is correct |
13 |
Correct |
82 ms |
25624 KB |
Output is correct |
14 |
Correct |
85 ms |
25624 KB |
Output is correct |
15 |
Correct |
54 ms |
25628 KB |
Output is correct |
16 |
Correct |
46 ms |
25672 KB |
Output is correct |
17 |
Correct |
71 ms |
25672 KB |
Output is correct |
18 |
Correct |
82 ms |
25672 KB |
Output is correct |
19 |
Correct |
85 ms |
25672 KB |
Output is correct |
20 |
Correct |
57 ms |
25672 KB |
Output is correct |
21 |
Correct |
46 ms |
25672 KB |
Output is correct |
22 |
Correct |
48 ms |
25672 KB |
Output is correct |
23 |
Correct |
664 ms |
53792 KB |
Output is correct |
24 |
Correct |
486 ms |
53792 KB |
Output is correct |
25 |
Correct |
460 ms |
53792 KB |
Output is correct |
26 |
Correct |
455 ms |
53792 KB |
Output is correct |
27 |
Correct |
475 ms |
53792 KB |
Output is correct |
28 |
Correct |
441 ms |
53792 KB |
Output is correct |
29 |
Correct |
462 ms |
53792 KB |
Output is correct |
30 |
Correct |
458 ms |
53820 KB |
Output is correct |
31 |
Correct |
461 ms |
53820 KB |
Output is correct |
32 |
Correct |
465 ms |
53820 KB |
Output is correct |
33 |
Correct |
81 ms |
53820 KB |
Output is correct |
34 |
Correct |
115 ms |
53820 KB |
Output is correct |
35 |
Correct |
459 ms |
53820 KB |
Output is correct |
36 |
Correct |
686 ms |
53820 KB |
Output is correct |
37 |
Correct |
407 ms |
53820 KB |
Output is correct |
38 |
Correct |
554 ms |
53820 KB |
Output is correct |
39 |
Correct |
447 ms |
53820 KB |
Output is correct |
40 |
Correct |
465 ms |
53872 KB |
Output is correct |
41 |
Correct |
510 ms |
53884 KB |
Output is correct |
42 |
Correct |
479 ms |
53952 KB |
Output is correct |
43 |
Correct |
433 ms |
53952 KB |
Output is correct |
44 |
Correct |
105 ms |
53952 KB |
Output is correct |
45 |
Correct |
204 ms |
53952 KB |
Output is correct |
46 |
Correct |
189 ms |
53952 KB |
Output is correct |
47 |
Correct |
200 ms |
53952 KB |
Output is correct |
48 |
Correct |
240 ms |
53952 KB |
Output is correct |
49 |
Correct |
632 ms |
54228 KB |
Output is correct |
50 |
Correct |
689 ms |
54336 KB |
Output is correct |
51 |
Correct |
626 ms |
54336 KB |
Output is correct |
52 |
Correct |
929 ms |
54464 KB |
Output is correct |
53 |
Correct |
602 ms |
54464 KB |
Output is correct |
54 |
Correct |
599 ms |
54464 KB |
Output is correct |
55 |
Correct |
632 ms |
54464 KB |
Output is correct |
56 |
Correct |
300 ms |
54464 KB |
Output is correct |
57 |
Correct |
490 ms |
54464 KB |
Output is correct |
58 |
Correct |
554 ms |
54464 KB |
Output is correct |
59 |
Correct |
1106 ms |
54464 KB |
Output is correct |
60 |
Correct |
1482 ms |
54464 KB |
Output is correct |
61 |
Correct |
953 ms |
54464 KB |
Output is correct |
62 |
Correct |
697 ms |
54464 KB |
Output is correct |
63 |
Correct |
1231 ms |
54464 KB |
Output is correct |
64 |
Correct |
1071 ms |
54528 KB |
Output is correct |
65 |
Correct |
877 ms |
54528 KB |
Output is correct |
66 |
Correct |
1063 ms |
54528 KB |
Output is correct |
67 |
Correct |
1044 ms |
54528 KB |
Output is correct |
68 |
Correct |
849 ms |
54528 KB |
Output is correct |
69 |
Correct |
1182 ms |
54528 KB |
Output is correct |