# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
287974 |
2020-09-01T07:21:49 Z |
Noam13 |
Seats (IOI18_seats) |
C++14 |
|
2711 ms |
99556 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vi>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define pb push_back
#define ii pair<int, int>
#define vii vector<ii>
#define x first
#define y second
#define all(a) a.begin(),a.end()
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;
const int INF = 1e9;
const int N = 1<<21;
int prop[N] = {0};
ii st[N];
void setp(int cur, int p){
prop[cur]+=p;
st[cur].x+=p;
}
void pull(int cur){
st[cur] = {min(st[2*cur].x, st[2*cur+1].x),0};
if (st[cur].x>=st[2*cur].x) st[cur].y+=st[2*cur].y;
if (st[cur].x>=st[2*cur+1].x) st[cur].y+=st[2*cur+1].y;
}
void push(int cur){
setp(2*cur, prop[cur]);
setp(2*cur+1, prop[cur]);
prop[cur] = 0;
}
void build(int cur, int l, int r, vi& a){
if (l+1==r){
st[cur] = {a[l],1};
return ;
}
int mid = (l+r)/2;
build(2*cur, l, mid, a);
build(2*cur+1, mid, r, a);
pull(cur);
}
bool flag = 0; vi pref;
void update(int cur, int l, int r, int a, int b, int v){
if (!flag){
pref[a]++; pref[b]--;
return ;
}
if (a>=r || b<=l) return ;
if (a<=l && r<=b){
setp(cur, v);
return ;
}
int mid = (l+r)/2;
push(cur);
update(2*cur, l, mid, a,b,v);
update(2*cur+1, mid, r, a,b,v);
pull(cur);
}
int query(){
return st[1].y;
}
int n,m;
vvi vals;
vii pos;
void update(int i, int j, int v){
vi vs;
loop(a,0,2) loop(b,0,2) vs.pb(vals[i+a][j+b]);
sort(all(vs));
int a = vs[0], b = vs[1], c = vs[2], d = vs[3];
update(1, 0, n*m, a, b, v);
update(1, 0, n*m, c, d, v);
}
void give_initial_chart(int H, int W, vi R, vi C) {
n = H, m = W;
vals.resize(n+2, vi(m+2, n*m));
pos.resize(n*m);
loop(i,0,n*m) {
pos[i] = {R[i]+1, C[i]+1};
}
loop(i,0,n*m) vals[pos[i].x][pos[i].y] = i;
pref.resize(n*m+1,0);
loop(i,0,n+1){
loop(j,0,m+1){
update(i, j, 1);
}
}
loop(i,1,n*m) pref[i]+=pref[i-1];
build(1,0,n*m, pref);
flag = 1;
}
set<ii> working;
void Working(ii p){
int a = p.x, b = p.y;
working.insert({a,b});
working.insert({a-1,b});
working.insert({a,b-1});
working.insert({a-1,b-1});
}
int swap_seats(int a, int b) {
ii posa = pos[a], posb = pos[b];
working.clear();
Working(posa); Working(posb);
for(auto p:working) update(p.x, p.y, -1);
swap(vals[posa.x][posa.y], vals[posb.x][posb.y]);
for(auto p:working) update(p.x, p.y, 1);
swap(pos[a], pos[b]);
return query();
}
/*
clear
g++ seats2.cpp grader.cpp -o a ; ./a
1 5 3
0 0
0 1
0 2
0 3
0 4
0 1
0 3
4 0
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
512 KB |
Output is correct |
2 |
Correct |
37 ms |
532 KB |
Output is correct |
3 |
Correct |
51 ms |
512 KB |
Output is correct |
4 |
Correct |
37 ms |
512 KB |
Output is correct |
5 |
Correct |
34 ms |
632 KB |
Output is correct |
6 |
Correct |
46 ms |
512 KB |
Output is correct |
7 |
Correct |
52 ms |
544 KB |
Output is correct |
8 |
Correct |
45 ms |
512 KB |
Output is correct |
9 |
Correct |
44 ms |
504 KB |
Output is correct |
10 |
Correct |
48 ms |
512 KB |
Output is correct |
11 |
Correct |
49 ms |
512 KB |
Output is correct |
12 |
Correct |
35 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
512 KB |
Output is correct |
2 |
Correct |
37 ms |
532 KB |
Output is correct |
3 |
Correct |
51 ms |
512 KB |
Output is correct |
4 |
Correct |
37 ms |
512 KB |
Output is correct |
5 |
Correct |
34 ms |
632 KB |
Output is correct |
6 |
Correct |
46 ms |
512 KB |
Output is correct |
7 |
Correct |
52 ms |
544 KB |
Output is correct |
8 |
Correct |
45 ms |
512 KB |
Output is correct |
9 |
Correct |
44 ms |
504 KB |
Output is correct |
10 |
Correct |
48 ms |
512 KB |
Output is correct |
11 |
Correct |
49 ms |
512 KB |
Output is correct |
12 |
Correct |
35 ms |
512 KB |
Output is correct |
13 |
Correct |
104 ms |
1280 KB |
Output is correct |
14 |
Correct |
116 ms |
1400 KB |
Output is correct |
15 |
Correct |
75 ms |
1400 KB |
Output is correct |
16 |
Correct |
60 ms |
1792 KB |
Output is correct |
17 |
Correct |
87 ms |
1528 KB |
Output is correct |
18 |
Correct |
96 ms |
1280 KB |
Output is correct |
19 |
Correct |
83 ms |
1280 KB |
Output is correct |
20 |
Correct |
74 ms |
1656 KB |
Output is correct |
21 |
Correct |
62 ms |
1408 KB |
Output is correct |
22 |
Correct |
61 ms |
1912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
850 ms |
49064 KB |
Output is correct |
2 |
Correct |
712 ms |
54116 KB |
Output is correct |
3 |
Correct |
712 ms |
54116 KB |
Output is correct |
4 |
Correct |
697 ms |
64612 KB |
Output is correct |
5 |
Correct |
706 ms |
64740 KB |
Output is correct |
6 |
Correct |
713 ms |
64624 KB |
Output is correct |
7 |
Correct |
708 ms |
64632 KB |
Output is correct |
8 |
Correct |
709 ms |
64624 KB |
Output is correct |
9 |
Correct |
705 ms |
64624 KB |
Output is correct |
10 |
Correct |
687 ms |
64740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
1144 KB |
Output is correct |
2 |
Correct |
170 ms |
5848 KB |
Output is correct |
3 |
Correct |
683 ms |
48740 KB |
Output is correct |
4 |
Correct |
842 ms |
48740 KB |
Output is correct |
5 |
Correct |
796 ms |
56404 KB |
Output is correct |
6 |
Correct |
1092 ms |
99556 KB |
Output is correct |
7 |
Correct |
727 ms |
51272 KB |
Output is correct |
8 |
Correct |
703 ms |
48740 KB |
Output is correct |
9 |
Correct |
696 ms |
49128 KB |
Output is correct |
10 |
Correct |
728 ms |
53348 KB |
Output is correct |
11 |
Correct |
791 ms |
72076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
1396 KB |
Output is correct |
2 |
Correct |
252 ms |
1396 KB |
Output is correct |
3 |
Correct |
340 ms |
1524 KB |
Output is correct |
4 |
Correct |
430 ms |
1396 KB |
Output is correct |
5 |
Correct |
629 ms |
2304 KB |
Output is correct |
6 |
Correct |
1616 ms |
57628 KB |
Output is correct |
7 |
Correct |
1614 ms |
57656 KB |
Output is correct |
8 |
Correct |
1604 ms |
57496 KB |
Output is correct |
9 |
Correct |
1909 ms |
57752 KB |
Output is correct |
10 |
Correct |
1490 ms |
57628 KB |
Output is correct |
11 |
Correct |
1494 ms |
57524 KB |
Output is correct |
12 |
Correct |
1482 ms |
57624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
512 KB |
Output is correct |
2 |
Correct |
37 ms |
532 KB |
Output is correct |
3 |
Correct |
51 ms |
512 KB |
Output is correct |
4 |
Correct |
37 ms |
512 KB |
Output is correct |
5 |
Correct |
34 ms |
632 KB |
Output is correct |
6 |
Correct |
46 ms |
512 KB |
Output is correct |
7 |
Correct |
52 ms |
544 KB |
Output is correct |
8 |
Correct |
45 ms |
512 KB |
Output is correct |
9 |
Correct |
44 ms |
504 KB |
Output is correct |
10 |
Correct |
48 ms |
512 KB |
Output is correct |
11 |
Correct |
49 ms |
512 KB |
Output is correct |
12 |
Correct |
35 ms |
512 KB |
Output is correct |
13 |
Correct |
104 ms |
1280 KB |
Output is correct |
14 |
Correct |
116 ms |
1400 KB |
Output is correct |
15 |
Correct |
75 ms |
1400 KB |
Output is correct |
16 |
Correct |
60 ms |
1792 KB |
Output is correct |
17 |
Correct |
87 ms |
1528 KB |
Output is correct |
18 |
Correct |
96 ms |
1280 KB |
Output is correct |
19 |
Correct |
83 ms |
1280 KB |
Output is correct |
20 |
Correct |
74 ms |
1656 KB |
Output is correct |
21 |
Correct |
62 ms |
1408 KB |
Output is correct |
22 |
Correct |
61 ms |
1912 KB |
Output is correct |
23 |
Correct |
850 ms |
49064 KB |
Output is correct |
24 |
Correct |
712 ms |
54116 KB |
Output is correct |
25 |
Correct |
712 ms |
54116 KB |
Output is correct |
26 |
Correct |
697 ms |
64612 KB |
Output is correct |
27 |
Correct |
706 ms |
64740 KB |
Output is correct |
28 |
Correct |
713 ms |
64624 KB |
Output is correct |
29 |
Correct |
708 ms |
64632 KB |
Output is correct |
30 |
Correct |
709 ms |
64624 KB |
Output is correct |
31 |
Correct |
705 ms |
64624 KB |
Output is correct |
32 |
Correct |
687 ms |
64740 KB |
Output is correct |
33 |
Correct |
99 ms |
1144 KB |
Output is correct |
34 |
Correct |
170 ms |
5848 KB |
Output is correct |
35 |
Correct |
683 ms |
48740 KB |
Output is correct |
36 |
Correct |
842 ms |
48740 KB |
Output is correct |
37 |
Correct |
796 ms |
56404 KB |
Output is correct |
38 |
Correct |
1092 ms |
99556 KB |
Output is correct |
39 |
Correct |
727 ms |
51272 KB |
Output is correct |
40 |
Correct |
703 ms |
48740 KB |
Output is correct |
41 |
Correct |
696 ms |
49128 KB |
Output is correct |
42 |
Correct |
728 ms |
53348 KB |
Output is correct |
43 |
Correct |
791 ms |
72076 KB |
Output is correct |
44 |
Correct |
196 ms |
1396 KB |
Output is correct |
45 |
Correct |
252 ms |
1396 KB |
Output is correct |
46 |
Correct |
340 ms |
1524 KB |
Output is correct |
47 |
Correct |
430 ms |
1396 KB |
Output is correct |
48 |
Correct |
629 ms |
2304 KB |
Output is correct |
49 |
Correct |
1616 ms |
57628 KB |
Output is correct |
50 |
Correct |
1614 ms |
57656 KB |
Output is correct |
51 |
Correct |
1604 ms |
57496 KB |
Output is correct |
52 |
Correct |
1909 ms |
57752 KB |
Output is correct |
53 |
Correct |
1490 ms |
57628 KB |
Output is correct |
54 |
Correct |
1494 ms |
57524 KB |
Output is correct |
55 |
Correct |
1482 ms |
57624 KB |
Output is correct |
56 |
Correct |
261 ms |
2036 KB |
Output is correct |
57 |
Correct |
504 ms |
2164 KB |
Output is correct |
58 |
Correct |
841 ms |
2904 KB |
Output is correct |
59 |
Correct |
2025 ms |
66232 KB |
Output is correct |
60 |
Correct |
2711 ms |
66252 KB |
Output is correct |
61 |
Correct |
1819 ms |
66276 KB |
Output is correct |
62 |
Correct |
1650 ms |
70460 KB |
Output is correct |
63 |
Correct |
2453 ms |
69044 KB |
Output is correct |
64 |
Correct |
1938 ms |
67040 KB |
Output is correct |
65 |
Correct |
1774 ms |
66404 KB |
Output is correct |
66 |
Correct |
2078 ms |
66784 KB |
Output is correct |
67 |
Correct |
1940 ms |
71140 KB |
Output is correct |
68 |
Correct |
1703 ms |
80612 KB |
Output is correct |
69 |
Correct |
2413 ms |
89832 KB |
Output is correct |