# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
161826 |
2019-11-04T14:10:05 Z |
mhy908 |
Seats (IOI18_seats) |
C++14 |
|
3460 ms |
237520 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
void ADD(pii &a, pii b){
a.F+=b.F;
a.S+=b.S;
}
struct SEGMENT_TREE{
struct NODE{
int minnum;
pii minn, lazy;
}tree[4000010];
void maketree(int point, int num) {
if(num==1){
tree[point].minnum=1;
}
if(num<=1)return;
maketree(point*2, num-num/2);
maketree(point*2+1, num/2);
}
void propogate(int point){
ADD(tree[2*point].minn, tree[point].lazy);
ADD(tree[2*point+1].minn, tree[point].lazy);
ADD(tree[2*point].lazy, tree[point].lazy);
ADD(tree[2*point+1].lazy, tree[point].lazy);
tree[point].lazy=pii(0, 0);
}
void relaxnode(int point){
tree[point].minn=min(tree[point*2].minn, tree[point*2+1].minn);
tree[point].minnum=0;
if(tree[point].minn==tree[point*2].minn)tree[point].minnum+=tree[point*2].minnum;
if(tree[point].minn==tree[point*2+1].minn)tree[point].minnum+=tree[point*2+1].minnum;
}
void alterrange(int point, int a, int b, pii p, int st, int fin) {
if(fin<a||st>b)return;
if(st>=a&&fin<=b) {
ADD(tree[point].minn, p);
ADD(tree[point].lazy, p);
return;
}
propogate(point);
alterrange(point*2, a, b, p, st, (st+fin)/2);
alterrange(point*2+1, a, b, p, (st+fin)/2+1, fin);
relaxnode(point);
}
int query(){
return tree[1].minn==pii(4, 0)?tree[1].minnum:0;
}
}seg;
vector<vector<int> > grid;
vector<vector<int> > valid;
vector<int> r, c, upd;
int n, m;
pii temp[1000010];
void updateall()
{
sort(all(upd));
upd.resize(unique(all(upd))-upd.begin());
pii t=pii(0, 0);
for(int i=0; i<upd.size()-1; i++){
ADD(t, temp[upd[i]]);
seg.alterrange(1, upd[i], upd[i+1]-1, t, 0, m*n-1);
}
for(int i=0; i<upd.size(); i++)temp[upd[i]]=pii(0, 0);
vector<int>().swap(upd);
}
void update(int x, int y, int p)
{
if((valid[x][y]==0&&p==-1)||(valid[x][y]==1&&p==1))return;
valid[x][y]^=1;
vector<pii> tem;
tem.pb(mp(grid[x][y], 0));
tem.pb(mp(grid[x+1][y], 1));
tem.pb(mp(grid[x+1][y+1], 2));
tem.pb(mp(grid[x][y+1], 3));
sort(all(tem));
for(int i=0; i<3; i++){
int st=tem[i].F, fin=tem[i+1].F;
st=max(st, 0);
fin=min(fin, n*m);
if(st>=fin)continue;
pii up;
if(i==0)up=pii(p, 0);
if(i==1){
if((tem[0].S^tem[1].S)==2)up=pii(2*p, 0);
else continue;
}
if(i==2)up=pii(0, p);
ADD(temp[st], up);
ADD(temp[fin], pii(-up.F, -up.S));
upd.pb(st);
upd.pb(fin);
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
n=H;
m=W;
r=R;
c=C;
grid.resize(n+2);
valid.resize(n+1);
for(int i=0; i<grid.size(); i++)grid[i].resize(m+2);
for(int i=0; i<valid.size(); i++)valid[i].resize(m+1);
for(int i=0; i<grid.size(); i++)
for(int j=0; j<grid[i].size(); j++)
grid[i][j]=10000000;
for(int i=0; i<n*m; i++){
grid[r[i]+1][c[i]+1]=i;
}
seg.maketree(1, n*m);
for(int i=0; i<=n; i++){
for(int j=0; j<=m; j++){
update(i, j, 1);
}
}
}
int swap_seats(int a, int b){
for(int i=0; i<=1; i++){
for(int j=0; j<=1; j++){
update(r[a]+i, c[a]+j, -1);
update(r[b]+i, c[b]+j, -1);
}
}
swap(r[a], r[b]);
swap(c[a], c[b]);
swap(grid[r[a]+1][c[a]+1], grid[r[b]+1][c[b]+1]);
for(int i=0; i<=1; i++){
for(int j=0; j<=1; j++){
update(r[a]+i, c[a]+j, 1);
update(r[b]+i, c[b]+j, 1);
}
}
updateall();
return seg.query();
}
Compilation message
seats.cpp: In function 'void updateall()':
seats.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<upd.size()-1; i++){
~^~~~~~~~~~~~~
seats.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<upd.size(); i++)temp[upd[i]]=pii(0, 0);
~^~~~~~~~~~~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:109:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<grid.size(); i++)grid[i].resize(m+2);
~^~~~~~~~~~~~
seats.cpp:110:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<valid.size(); i++)valid[i].resize(m+1);
~^~~~~~~~~~~~~
seats.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<grid.size(); i++)
~^~~~~~~~~~~~
seats.cpp:112:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<grid[i].size(); j++)
~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
78836 KB |
Output is correct |
2 |
Correct |
107 ms |
78792 KB |
Output is correct |
3 |
Correct |
121 ms |
78812 KB |
Output is correct |
4 |
Correct |
102 ms |
78840 KB |
Output is correct |
5 |
Correct |
98 ms |
78812 KB |
Output is correct |
6 |
Correct |
114 ms |
78812 KB |
Output is correct |
7 |
Correct |
115 ms |
78812 KB |
Output is correct |
8 |
Correct |
114 ms |
78840 KB |
Output is correct |
9 |
Correct |
114 ms |
78840 KB |
Output is correct |
10 |
Correct |
117 ms |
78824 KB |
Output is correct |
11 |
Correct |
113 ms |
78840 KB |
Output is correct |
12 |
Correct |
96 ms |
78840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
78836 KB |
Output is correct |
2 |
Correct |
107 ms |
78792 KB |
Output is correct |
3 |
Correct |
121 ms |
78812 KB |
Output is correct |
4 |
Correct |
102 ms |
78840 KB |
Output is correct |
5 |
Correct |
98 ms |
78812 KB |
Output is correct |
6 |
Correct |
114 ms |
78812 KB |
Output is correct |
7 |
Correct |
115 ms |
78812 KB |
Output is correct |
8 |
Correct |
114 ms |
78840 KB |
Output is correct |
9 |
Correct |
114 ms |
78840 KB |
Output is correct |
10 |
Correct |
117 ms |
78824 KB |
Output is correct |
11 |
Correct |
113 ms |
78840 KB |
Output is correct |
12 |
Correct |
96 ms |
78840 KB |
Output is correct |
13 |
Correct |
162 ms |
79640 KB |
Output is correct |
14 |
Correct |
168 ms |
79600 KB |
Output is correct |
15 |
Correct |
130 ms |
79736 KB |
Output is correct |
16 |
Correct |
123 ms |
80632 KB |
Output is correct |
17 |
Correct |
145 ms |
79740 KB |
Output is correct |
18 |
Correct |
148 ms |
79608 KB |
Output is correct |
19 |
Correct |
179 ms |
79784 KB |
Output is correct |
20 |
Correct |
133 ms |
80096 KB |
Output is correct |
21 |
Correct |
123 ms |
79736 KB |
Output is correct |
22 |
Correct |
123 ms |
80764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2045 ms |
155052 KB |
Output is correct |
2 |
Correct |
1486 ms |
137060 KB |
Output is correct |
3 |
Correct |
1525 ms |
135504 KB |
Output is correct |
4 |
Correct |
1426 ms |
135736 KB |
Output is correct |
5 |
Correct |
1416 ms |
136152 KB |
Output is correct |
6 |
Correct |
1371 ms |
135496 KB |
Output is correct |
7 |
Correct |
1465 ms |
135692 KB |
Output is correct |
8 |
Correct |
1502 ms |
136236 KB |
Output is correct |
9 |
Correct |
1451 ms |
135696 KB |
Output is correct |
10 |
Correct |
1463 ms |
135812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
162 ms |
79608 KB |
Output is correct |
2 |
Correct |
284 ms |
85824 KB |
Output is correct |
3 |
Correct |
1775 ms |
135788 KB |
Output is correct |
4 |
Correct |
1922 ms |
153008 KB |
Output is correct |
5 |
Correct |
1740 ms |
148180 KB |
Output is correct |
6 |
Correct |
2362 ms |
237520 KB |
Output is correct |
7 |
Correct |
1438 ms |
139884 KB |
Output is correct |
8 |
Correct |
1448 ms |
136020 KB |
Output is correct |
9 |
Correct |
1553 ms |
135996 KB |
Output is correct |
10 |
Correct |
1498 ms |
144564 KB |
Output is correct |
11 |
Correct |
1635 ms |
181992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
266 ms |
80500 KB |
Output is correct |
2 |
Correct |
325 ms |
80400 KB |
Output is correct |
3 |
Correct |
339 ms |
80428 KB |
Output is correct |
4 |
Correct |
385 ms |
80604 KB |
Output is correct |
5 |
Correct |
495 ms |
81048 KB |
Output is correct |
6 |
Correct |
2259 ms |
146588 KB |
Output is correct |
7 |
Correct |
2166 ms |
146672 KB |
Output is correct |
8 |
Correct |
2253 ms |
146652 KB |
Output is correct |
9 |
Correct |
2748 ms |
146616 KB |
Output is correct |
10 |
Correct |
2215 ms |
146564 KB |
Output is correct |
11 |
Correct |
2286 ms |
146556 KB |
Output is correct |
12 |
Correct |
2153 ms |
146548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
78836 KB |
Output is correct |
2 |
Correct |
107 ms |
78792 KB |
Output is correct |
3 |
Correct |
121 ms |
78812 KB |
Output is correct |
4 |
Correct |
102 ms |
78840 KB |
Output is correct |
5 |
Correct |
98 ms |
78812 KB |
Output is correct |
6 |
Correct |
114 ms |
78812 KB |
Output is correct |
7 |
Correct |
115 ms |
78812 KB |
Output is correct |
8 |
Correct |
114 ms |
78840 KB |
Output is correct |
9 |
Correct |
114 ms |
78840 KB |
Output is correct |
10 |
Correct |
117 ms |
78824 KB |
Output is correct |
11 |
Correct |
113 ms |
78840 KB |
Output is correct |
12 |
Correct |
96 ms |
78840 KB |
Output is correct |
13 |
Correct |
162 ms |
79640 KB |
Output is correct |
14 |
Correct |
168 ms |
79600 KB |
Output is correct |
15 |
Correct |
130 ms |
79736 KB |
Output is correct |
16 |
Correct |
123 ms |
80632 KB |
Output is correct |
17 |
Correct |
145 ms |
79740 KB |
Output is correct |
18 |
Correct |
148 ms |
79608 KB |
Output is correct |
19 |
Correct |
179 ms |
79784 KB |
Output is correct |
20 |
Correct |
133 ms |
80096 KB |
Output is correct |
21 |
Correct |
123 ms |
79736 KB |
Output is correct |
22 |
Correct |
123 ms |
80764 KB |
Output is correct |
23 |
Correct |
2045 ms |
155052 KB |
Output is correct |
24 |
Correct |
1486 ms |
137060 KB |
Output is correct |
25 |
Correct |
1525 ms |
135504 KB |
Output is correct |
26 |
Correct |
1426 ms |
135736 KB |
Output is correct |
27 |
Correct |
1416 ms |
136152 KB |
Output is correct |
28 |
Correct |
1371 ms |
135496 KB |
Output is correct |
29 |
Correct |
1465 ms |
135692 KB |
Output is correct |
30 |
Correct |
1502 ms |
136236 KB |
Output is correct |
31 |
Correct |
1451 ms |
135696 KB |
Output is correct |
32 |
Correct |
1463 ms |
135812 KB |
Output is correct |
33 |
Correct |
162 ms |
79608 KB |
Output is correct |
34 |
Correct |
284 ms |
85824 KB |
Output is correct |
35 |
Correct |
1775 ms |
135788 KB |
Output is correct |
36 |
Correct |
1922 ms |
153008 KB |
Output is correct |
37 |
Correct |
1740 ms |
148180 KB |
Output is correct |
38 |
Correct |
2362 ms |
237520 KB |
Output is correct |
39 |
Correct |
1438 ms |
139884 KB |
Output is correct |
40 |
Correct |
1448 ms |
136020 KB |
Output is correct |
41 |
Correct |
1553 ms |
135996 KB |
Output is correct |
42 |
Correct |
1498 ms |
144564 KB |
Output is correct |
43 |
Correct |
1635 ms |
181992 KB |
Output is correct |
44 |
Correct |
266 ms |
80500 KB |
Output is correct |
45 |
Correct |
325 ms |
80400 KB |
Output is correct |
46 |
Correct |
339 ms |
80428 KB |
Output is correct |
47 |
Correct |
385 ms |
80604 KB |
Output is correct |
48 |
Correct |
495 ms |
81048 KB |
Output is correct |
49 |
Correct |
2259 ms |
146588 KB |
Output is correct |
50 |
Correct |
2166 ms |
146672 KB |
Output is correct |
51 |
Correct |
2253 ms |
146652 KB |
Output is correct |
52 |
Correct |
2748 ms |
146616 KB |
Output is correct |
53 |
Correct |
2215 ms |
146564 KB |
Output is correct |
54 |
Correct |
2286 ms |
146556 KB |
Output is correct |
55 |
Correct |
2153 ms |
146548 KB |
Output is correct |
56 |
Correct |
376 ms |
80376 KB |
Output is correct |
57 |
Correct |
569 ms |
80616 KB |
Output is correct |
58 |
Correct |
832 ms |
81036 KB |
Output is correct |
59 |
Correct |
2541 ms |
134296 KB |
Output is correct |
60 |
Correct |
3460 ms |
151364 KB |
Output is correct |
61 |
Correct |
2324 ms |
134172 KB |
Output is correct |
62 |
Correct |
2179 ms |
140064 KB |
Output is correct |
63 |
Correct |
3252 ms |
155200 KB |
Output is correct |
64 |
Correct |
2581 ms |
136048 KB |
Output is correct |
65 |
Correct |
2273 ms |
134972 KB |
Output is correct |
66 |
Correct |
2725 ms |
134724 KB |
Output is correct |
67 |
Correct |
2637 ms |
144188 KB |
Output is correct |
68 |
Correct |
2255 ms |
162792 KB |
Output is correct |
69 |
Correct |
3348 ms |
198168 KB |
Output is correct |