# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
900410 |
2024-01-08T09:01:44 Z |
12345678 |
Seats (IOI18_seats) |
C++17 |
|
1219 ms |
115252 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e6+5;
int N, h, w, r[nx], c[nx], dp[nx], tmp[5][5], mp[5][5], dx[]={-1, -1, -1, 0, 0, 0, 1, 1, 1}, dy[]={-1, 0, 1, -1, 0, 1, -1, 0, 1};
vector<vector<int>> v;
struct segtree
{
struct node
{
int mn, f, lz;
} d[4*nx];
node merge(node a, node b)
{
if (a.mn==b.mn) a.f+=b.f;
if (a.mn<=b.mn) return a;
else return b;
}
void pushlz(int l, int r, int i)
{
if (l==r) return d[i].mn+=d[i].lz, d[i].lz=0, void();
d[2*i].lz+=d[i].lz;
d[2*i+1].lz+=d[i].lz;
d[i].mn+=d[i].lz;
d[i].lz=0;
}
void build(int l, int r, int i)
{
if (l==r) return void(d[i].f=1);
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=merge(d[2*i], d[2*i+1]);
}
void update(int l, int r, int i, int ql, int qr, int vl)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return d[i].lz=vl, pushlz(l, r, i), void();
int md=(l+r)/2;
update(l, md, 2*i, ql, qr, vl);
update(md+1, r, 2*i+1, ql, qr, vl);
d[i]=merge(d[2*i], d[2*i+1]);
}
} s;
int solve()
{
int cnt=0;
for (int i=0; i<5; i++) for (int j=0; j<5; j++) tmp[i][j]=0;
for (int i=1; i<=4; i++) for (int j=1; j<=3; j++) if (mp[i][j]+mp[i-1][j]==1) tmp[i][j]=1;
for (int i=1; i<=4; i++) for (int j=1; j<=3; j++) cnt+=(tmp[i][j]&&(!tmp[i][j-1]));
for (int i=0; i<5; i++) for (int j=0; j<5; j++) tmp[i][j]=0;
for (int i=1; i<=3; i++) for (int j=1; j<=4; j++) if (mp[i][j]+mp[i][j-1]==1) tmp[i][j]=1;
for (int i=1; i<=3; i++) for (int j=1; j<=4; j++) cnt+=(tmp[i][j]&&(!tmp[i-1][j]));
return cnt;
}
void precompute()
{
for (int i=0; i<(1<<9); i++)
{
if (i&(1<<4)) continue;
for (int j=0; j<9; j++) mp[j/3+1][(j%3)+1]=(i&(1<<j))>0;
dp[i]=-solve();
mp[2][2]=1;
dp[i]+=solve();
}
}
void updateseats(int x, int y, int mul)
{
if (x==0||x==h+1||y==0||y==w+1) return;
int c=0;
for (int i=0; i<9; i++) if (i!=4&&v[x+dx[i]][y+dy[i]]<v[x][y]) c|=(1<<i);
s.update(1, N, 1, v[x][y], N, mul*dp[c]);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h=H; w=W; N=h*w;
v.resize(h+2);
for (int i=0; i<h+2; i++) v[i].resize(w+2);
for (int i=0; i<h+2; i++) for (int j=0; j<w+2; j++) v[i][j]=1e9;
for (int i=1; i<=N; i++) r[i]=R[i-1]+1;
for (int i=1; i<=N; i++) c[i]=C[i-1]+1;
for (int i=1; i<=N; i++) v[r[i]][c[i]]=i;
s.build(1, N, 1);
precompute();
for (int i=1; i<=N; i++) updateseats(r[i], c[i], 1);
}
int swap_seats(int a, int b) {
a++; b++;
set<pair<int, int>> upd;
for (int i=-1; i<=1; i++) for (int j=-1; j<=1; j++) upd.insert({r[a]+i, c[a]+j}), upd.insert({r[b]+i, c[b]+j});
for (auto [x, y]:upd) updateseats(x, y, -1);
swap(v[r[a]][c[a]], v[r[b]][c[b]]);
swap(r[a], r[b]);
swap(c[a], c[b]);
for (auto [x, y]:upd) updateseats(x, y, 1);
return s.d[1].f;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
6744 KB |
Output is correct |
2 |
Correct |
19 ms |
6712 KB |
Output is correct |
3 |
Correct |
28 ms |
6716 KB |
Output is correct |
4 |
Correct |
18 ms |
6748 KB |
Output is correct |
5 |
Correct |
12 ms |
6720 KB |
Output is correct |
6 |
Correct |
22 ms |
6732 KB |
Output is correct |
7 |
Correct |
24 ms |
6748 KB |
Output is correct |
8 |
Correct |
25 ms |
6740 KB |
Output is correct |
9 |
Correct |
24 ms |
6744 KB |
Output is correct |
10 |
Correct |
25 ms |
6728 KB |
Output is correct |
11 |
Correct |
26 ms |
6740 KB |
Output is correct |
12 |
Correct |
13 ms |
6744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
6744 KB |
Output is correct |
2 |
Correct |
19 ms |
6712 KB |
Output is correct |
3 |
Correct |
28 ms |
6716 KB |
Output is correct |
4 |
Correct |
18 ms |
6748 KB |
Output is correct |
5 |
Correct |
12 ms |
6720 KB |
Output is correct |
6 |
Correct |
22 ms |
6732 KB |
Output is correct |
7 |
Correct |
24 ms |
6748 KB |
Output is correct |
8 |
Correct |
25 ms |
6740 KB |
Output is correct |
9 |
Correct |
24 ms |
6744 KB |
Output is correct |
10 |
Correct |
25 ms |
6728 KB |
Output is correct |
11 |
Correct |
26 ms |
6740 KB |
Output is correct |
12 |
Correct |
13 ms |
6744 KB |
Output is correct |
13 |
Correct |
55 ms |
9220 KB |
Output is correct |
14 |
Correct |
51 ms |
9048 KB |
Output is correct |
15 |
Correct |
23 ms |
9304 KB |
Output is correct |
16 |
Correct |
27 ms |
9560 KB |
Output is correct |
17 |
Correct |
37 ms |
9052 KB |
Output is correct |
18 |
Correct |
48 ms |
9224 KB |
Output is correct |
19 |
Correct |
46 ms |
9052 KB |
Output is correct |
20 |
Correct |
37 ms |
9576 KB |
Output is correct |
21 |
Correct |
22 ms |
9308 KB |
Output is correct |
22 |
Correct |
23 ms |
9564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
538 ms |
64568 KB |
Output is correct |
2 |
Correct |
567 ms |
64184 KB |
Output is correct |
3 |
Correct |
491 ms |
64416 KB |
Output is correct |
4 |
Correct |
471 ms |
64184 KB |
Output is correct |
5 |
Correct |
512 ms |
64408 KB |
Output is correct |
6 |
Correct |
472 ms |
64412 KB |
Output is correct |
7 |
Correct |
458 ms |
64420 KB |
Output is correct |
8 |
Correct |
468 ms |
64596 KB |
Output is correct |
9 |
Correct |
476 ms |
64412 KB |
Output is correct |
10 |
Correct |
478 ms |
64420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
9236 KB |
Output is correct |
2 |
Correct |
88 ms |
13656 KB |
Output is correct |
3 |
Correct |
513 ms |
64412 KB |
Output is correct |
4 |
Correct |
544 ms |
64340 KB |
Output is correct |
5 |
Correct |
429 ms |
72200 KB |
Output is correct |
6 |
Correct |
734 ms |
115252 KB |
Output is correct |
7 |
Correct |
482 ms |
66984 KB |
Output is correct |
8 |
Correct |
490 ms |
64340 KB |
Output is correct |
9 |
Correct |
466 ms |
64764 KB |
Output is correct |
10 |
Correct |
502 ms |
69064 KB |
Output is correct |
11 |
Correct |
483 ms |
87852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
8140 KB |
Output is correct |
2 |
Correct |
85 ms |
7988 KB |
Output is correct |
3 |
Correct |
124 ms |
8088 KB |
Output is correct |
4 |
Correct |
147 ms |
8076 KB |
Output is correct |
5 |
Correct |
183 ms |
10700 KB |
Output is correct |
6 |
Correct |
690 ms |
72924 KB |
Output is correct |
7 |
Correct |
721 ms |
73116 KB |
Output is correct |
8 |
Correct |
662 ms |
73252 KB |
Output is correct |
9 |
Correct |
751 ms |
73064 KB |
Output is correct |
10 |
Correct |
657 ms |
73068 KB |
Output is correct |
11 |
Correct |
656 ms |
73060 KB |
Output is correct |
12 |
Correct |
619 ms |
73036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
6744 KB |
Output is correct |
2 |
Correct |
19 ms |
6712 KB |
Output is correct |
3 |
Correct |
28 ms |
6716 KB |
Output is correct |
4 |
Correct |
18 ms |
6748 KB |
Output is correct |
5 |
Correct |
12 ms |
6720 KB |
Output is correct |
6 |
Correct |
22 ms |
6732 KB |
Output is correct |
7 |
Correct |
24 ms |
6748 KB |
Output is correct |
8 |
Correct |
25 ms |
6740 KB |
Output is correct |
9 |
Correct |
24 ms |
6744 KB |
Output is correct |
10 |
Correct |
25 ms |
6728 KB |
Output is correct |
11 |
Correct |
26 ms |
6740 KB |
Output is correct |
12 |
Correct |
13 ms |
6744 KB |
Output is correct |
13 |
Correct |
55 ms |
9220 KB |
Output is correct |
14 |
Correct |
51 ms |
9048 KB |
Output is correct |
15 |
Correct |
23 ms |
9304 KB |
Output is correct |
16 |
Correct |
27 ms |
9560 KB |
Output is correct |
17 |
Correct |
37 ms |
9052 KB |
Output is correct |
18 |
Correct |
48 ms |
9224 KB |
Output is correct |
19 |
Correct |
46 ms |
9052 KB |
Output is correct |
20 |
Correct |
37 ms |
9576 KB |
Output is correct |
21 |
Correct |
22 ms |
9308 KB |
Output is correct |
22 |
Correct |
23 ms |
9564 KB |
Output is correct |
23 |
Correct |
538 ms |
64568 KB |
Output is correct |
24 |
Correct |
567 ms |
64184 KB |
Output is correct |
25 |
Correct |
491 ms |
64416 KB |
Output is correct |
26 |
Correct |
471 ms |
64184 KB |
Output is correct |
27 |
Correct |
512 ms |
64408 KB |
Output is correct |
28 |
Correct |
472 ms |
64412 KB |
Output is correct |
29 |
Correct |
458 ms |
64420 KB |
Output is correct |
30 |
Correct |
468 ms |
64596 KB |
Output is correct |
31 |
Correct |
476 ms |
64412 KB |
Output is correct |
32 |
Correct |
478 ms |
64420 KB |
Output is correct |
33 |
Correct |
50 ms |
9236 KB |
Output is correct |
34 |
Correct |
88 ms |
13656 KB |
Output is correct |
35 |
Correct |
513 ms |
64412 KB |
Output is correct |
36 |
Correct |
544 ms |
64340 KB |
Output is correct |
37 |
Correct |
429 ms |
72200 KB |
Output is correct |
38 |
Correct |
734 ms |
115252 KB |
Output is correct |
39 |
Correct |
482 ms |
66984 KB |
Output is correct |
40 |
Correct |
490 ms |
64340 KB |
Output is correct |
41 |
Correct |
466 ms |
64764 KB |
Output is correct |
42 |
Correct |
502 ms |
69064 KB |
Output is correct |
43 |
Correct |
483 ms |
87852 KB |
Output is correct |
44 |
Correct |
51 ms |
8140 KB |
Output is correct |
45 |
Correct |
85 ms |
7988 KB |
Output is correct |
46 |
Correct |
124 ms |
8088 KB |
Output is correct |
47 |
Correct |
147 ms |
8076 KB |
Output is correct |
48 |
Correct |
183 ms |
10700 KB |
Output is correct |
49 |
Correct |
690 ms |
72924 KB |
Output is correct |
50 |
Correct |
721 ms |
73116 KB |
Output is correct |
51 |
Correct |
662 ms |
73252 KB |
Output is correct |
52 |
Correct |
751 ms |
73064 KB |
Output is correct |
53 |
Correct |
657 ms |
73068 KB |
Output is correct |
54 |
Correct |
656 ms |
73060 KB |
Output is correct |
55 |
Correct |
619 ms |
73036 KB |
Output is correct |
56 |
Correct |
115 ms |
8132 KB |
Output is correct |
57 |
Correct |
258 ms |
8132 KB |
Output is correct |
58 |
Correct |
453 ms |
11040 KB |
Output is correct |
59 |
Correct |
1070 ms |
65024 KB |
Output is correct |
60 |
Correct |
1219 ms |
56656 KB |
Output is correct |
61 |
Correct |
1020 ms |
56652 KB |
Output is correct |
62 |
Correct |
788 ms |
60244 KB |
Output is correct |
63 |
Correct |
1082 ms |
59096 KB |
Output is correct |
64 |
Correct |
1076 ms |
57328 KB |
Output is correct |
65 |
Correct |
997 ms |
56408 KB |
Output is correct |
66 |
Correct |
1094 ms |
56908 KB |
Output is correct |
67 |
Correct |
1055 ms |
61260 KB |
Output is correct |
68 |
Correct |
914 ms |
70736 KB |
Output is correct |
69 |
Correct |
1161 ms |
80012 KB |
Output is correct |