# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
419306 |
2021-06-06T20:26:45 Z |
Antekb |
Seats (IOI18_seats) |
C++14 |
|
2864 ms |
126684 KB |
#include "seats.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
vector<int> R, C;
int h, w;
const int N=(1<<20);
int mini[2*N], ile[2*N], lazy[2*N];
void prop(int v){
if(!lazy[v])return;
int l=v+v, r=l+1;
lazy[l]+=lazy[v];
lazy[r]+=lazy[v];
mini[l]+=lazy[v];
mini[r]+=lazy[v];
lazy[v]=0;
}
void upd(int v){
int l=v+v, r=l+1;
ile[v]=0;
if(mini[l]<=mini[r])ile[v]+=ile[l], mini[v]=mini[l];
if(mini[r]<=mini[l])ile[v]+=ile[r], mini[v]=mini[r];
}
void add(int v, int L, int R, int l, int r, int c){
if(l==L && r==R){
lazy[v]+=c;
mini[v]+=c;
return;
}
int M=(L+R)>>1;
prop(v);
if(M>=l)add(2*v, L, M, l, min(M, r), c);
if(r>M)add(2*v+1, M+1, R, max(M+1, l), r, c);
upd(v);
return;
}
vector<vector<int> > co;
void Set(int x, int y, int c){
int tab[4]={co[x][y], co[x+1][y], co[x][y+1], co[x+1][y+1]};
sort(tab, tab+4);
//cerr<<x<<" "<<y<<"\n";
//cerr<<tab[0]<<" "<<tab[1]-1<<" "<<c<<"\n";
//cerr<<tab[2]<<" "<<tab[3]-1<<" "<<c<<"\n";
if(tab[0]<tab[1])add(1, 0, N-1, tab[0], tab[1]-1, c);
if(tab[2]<tab[3])add(1, 0, N-1, tab[2], tab[3]-1, c);
}
void give_initial_chart(int H, int W, std::vector<int> R2, std::vector<int> C2) {
R=R2;
C=C2;
h=H;
w=W;
co.resize(h+2, vector<int>(w+2, h*w));
for(int i=0; i<h*w; i++){
R[i]++;
C[i]++;
co[R[i]][C[i]]=i;
ile[N+i]=1;
}
for(int i=h*w; i<N; i++){
ile[N+i]=1;
mini[N+i]=2*N;
}
//cerr<<ile[1]<<"\n";
vector<pair<int, int> > V;
for(int i=0; i<=h; i++){
for(int j=0; j<=w; j++){
int tab[4]={co[i][j], co[i+1][j], co[i][j+1], co[i+1][j+1]};
sort(tab, tab+4);
if(tab[0]<tab[1])V.push_back({tab[0], 1}), V.push_back({tab[1], -1});
if(tab[2]<tab[3])V.push_back({tab[2], 1}), V.push_back({tab[3], -1});
}
}
sort(V.begin(), V.end());
int wsk=0;
int cnt=0;
for(int i=0; i<h*w; i++){
while(wsk<V.size() && V[wsk].st==i){
cnt+=V[wsk++].nd;
}
mini[N+i]=cnt;
}
for(int i=N-1; i>0; i--)upd(i);
//cerr<<ile[1]<<"\n";
}
void Setall(int x, int y, int c){
Set(x, y, c);
Set(x-1, y, c);
Set(x, y-1, c);
Set(x-1, y-1, c);
}
int swap_seats(int a, int b) {
//return -1;
Setall(R[a], C[a], -1);
Setall(R[b], C[b], -1);
swap(R[a], R[b]);
swap(C[a], C[b]);
swap(co[R[a]][C[a]], co[R[b]][C[b]]);
Setall(R[a], C[a], 1);
Setall(R[b], C[b], 1);
return ile[1];
}
Compilation message
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:78:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | while(wsk<V.size() && V[wsk].st==i){
| ~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
16948 KB |
Output is correct |
2 |
Correct |
80 ms |
16828 KB |
Output is correct |
3 |
Correct |
90 ms |
16840 KB |
Output is correct |
4 |
Correct |
56 ms |
16880 KB |
Output is correct |
5 |
Correct |
52 ms |
16856 KB |
Output is correct |
6 |
Correct |
76 ms |
16860 KB |
Output is correct |
7 |
Correct |
82 ms |
16852 KB |
Output is correct |
8 |
Correct |
82 ms |
16924 KB |
Output is correct |
9 |
Correct |
83 ms |
16836 KB |
Output is correct |
10 |
Correct |
82 ms |
16812 KB |
Output is correct |
11 |
Correct |
79 ms |
16844 KB |
Output is correct |
12 |
Correct |
54 ms |
16852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
16948 KB |
Output is correct |
2 |
Correct |
80 ms |
16828 KB |
Output is correct |
3 |
Correct |
90 ms |
16840 KB |
Output is correct |
4 |
Correct |
56 ms |
16880 KB |
Output is correct |
5 |
Correct |
52 ms |
16856 KB |
Output is correct |
6 |
Correct |
76 ms |
16860 KB |
Output is correct |
7 |
Correct |
82 ms |
16852 KB |
Output is correct |
8 |
Correct |
82 ms |
16924 KB |
Output is correct |
9 |
Correct |
83 ms |
16836 KB |
Output is correct |
10 |
Correct |
82 ms |
16812 KB |
Output is correct |
11 |
Correct |
79 ms |
16844 KB |
Output is correct |
12 |
Correct |
54 ms |
16852 KB |
Output is correct |
13 |
Correct |
114 ms |
17576 KB |
Output is correct |
14 |
Correct |
127 ms |
17556 KB |
Output is correct |
15 |
Correct |
74 ms |
17684 KB |
Output is correct |
16 |
Correct |
59 ms |
18056 KB |
Output is correct |
17 |
Correct |
90 ms |
17592 KB |
Output is correct |
18 |
Correct |
98 ms |
17564 KB |
Output is correct |
19 |
Correct |
90 ms |
17576 KB |
Output is correct |
20 |
Correct |
76 ms |
17700 KB |
Output is correct |
21 |
Correct |
76 ms |
17712 KB |
Output is correct |
22 |
Correct |
61 ms |
18100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1091 ms |
75880 KB |
Output is correct |
2 |
Correct |
884 ms |
76320 KB |
Output is correct |
3 |
Correct |
868 ms |
76200 KB |
Output is correct |
4 |
Correct |
789 ms |
75852 KB |
Output is correct |
5 |
Correct |
757 ms |
75896 KB |
Output is correct |
6 |
Correct |
709 ms |
75856 KB |
Output is correct |
7 |
Correct |
856 ms |
75880 KB |
Output is correct |
8 |
Correct |
949 ms |
75860 KB |
Output is correct |
9 |
Correct |
861 ms |
75888 KB |
Output is correct |
10 |
Correct |
823 ms |
75852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
17596 KB |
Output is correct |
2 |
Correct |
180 ms |
22448 KB |
Output is correct |
3 |
Correct |
839 ms |
76140 KB |
Output is correct |
4 |
Correct |
1107 ms |
76008 KB |
Output is correct |
5 |
Correct |
1051 ms |
87844 KB |
Output is correct |
6 |
Correct |
1231 ms |
126684 KB |
Output is correct |
7 |
Correct |
781 ms |
80372 KB |
Output is correct |
8 |
Correct |
835 ms |
75936 KB |
Output is correct |
9 |
Correct |
929 ms |
76248 KB |
Output is correct |
10 |
Correct |
851 ms |
80532 KB |
Output is correct |
11 |
Correct |
629 ms |
99300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
434 ms |
17824 KB |
Output is correct |
2 |
Correct |
427 ms |
18056 KB |
Output is correct |
3 |
Correct |
406 ms |
17984 KB |
Output is correct |
4 |
Correct |
437 ms |
18032 KB |
Output is correct |
5 |
Correct |
551 ms |
18656 KB |
Output is correct |
6 |
Correct |
1573 ms |
87796 KB |
Output is correct |
7 |
Correct |
1385 ms |
87952 KB |
Output is correct |
8 |
Correct |
1602 ms |
87748 KB |
Output is correct |
9 |
Correct |
1763 ms |
87812 KB |
Output is correct |
10 |
Correct |
1439 ms |
87740 KB |
Output is correct |
11 |
Correct |
1501 ms |
87716 KB |
Output is correct |
12 |
Correct |
1416 ms |
87760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
16948 KB |
Output is correct |
2 |
Correct |
80 ms |
16828 KB |
Output is correct |
3 |
Correct |
90 ms |
16840 KB |
Output is correct |
4 |
Correct |
56 ms |
16880 KB |
Output is correct |
5 |
Correct |
52 ms |
16856 KB |
Output is correct |
6 |
Correct |
76 ms |
16860 KB |
Output is correct |
7 |
Correct |
82 ms |
16852 KB |
Output is correct |
8 |
Correct |
82 ms |
16924 KB |
Output is correct |
9 |
Correct |
83 ms |
16836 KB |
Output is correct |
10 |
Correct |
82 ms |
16812 KB |
Output is correct |
11 |
Correct |
79 ms |
16844 KB |
Output is correct |
12 |
Correct |
54 ms |
16852 KB |
Output is correct |
13 |
Correct |
114 ms |
17576 KB |
Output is correct |
14 |
Correct |
127 ms |
17556 KB |
Output is correct |
15 |
Correct |
74 ms |
17684 KB |
Output is correct |
16 |
Correct |
59 ms |
18056 KB |
Output is correct |
17 |
Correct |
90 ms |
17592 KB |
Output is correct |
18 |
Correct |
98 ms |
17564 KB |
Output is correct |
19 |
Correct |
90 ms |
17576 KB |
Output is correct |
20 |
Correct |
76 ms |
17700 KB |
Output is correct |
21 |
Correct |
76 ms |
17712 KB |
Output is correct |
22 |
Correct |
61 ms |
18100 KB |
Output is correct |
23 |
Correct |
1091 ms |
75880 KB |
Output is correct |
24 |
Correct |
884 ms |
76320 KB |
Output is correct |
25 |
Correct |
868 ms |
76200 KB |
Output is correct |
26 |
Correct |
789 ms |
75852 KB |
Output is correct |
27 |
Correct |
757 ms |
75896 KB |
Output is correct |
28 |
Correct |
709 ms |
75856 KB |
Output is correct |
29 |
Correct |
856 ms |
75880 KB |
Output is correct |
30 |
Correct |
949 ms |
75860 KB |
Output is correct |
31 |
Correct |
861 ms |
75888 KB |
Output is correct |
32 |
Correct |
823 ms |
75852 KB |
Output is correct |
33 |
Correct |
110 ms |
17596 KB |
Output is correct |
34 |
Correct |
180 ms |
22448 KB |
Output is correct |
35 |
Correct |
839 ms |
76140 KB |
Output is correct |
36 |
Correct |
1107 ms |
76008 KB |
Output is correct |
37 |
Correct |
1051 ms |
87844 KB |
Output is correct |
38 |
Correct |
1231 ms |
126684 KB |
Output is correct |
39 |
Correct |
781 ms |
80372 KB |
Output is correct |
40 |
Correct |
835 ms |
75936 KB |
Output is correct |
41 |
Correct |
929 ms |
76248 KB |
Output is correct |
42 |
Correct |
851 ms |
80532 KB |
Output is correct |
43 |
Correct |
629 ms |
99300 KB |
Output is correct |
44 |
Correct |
434 ms |
17824 KB |
Output is correct |
45 |
Correct |
427 ms |
18056 KB |
Output is correct |
46 |
Correct |
406 ms |
17984 KB |
Output is correct |
47 |
Correct |
437 ms |
18032 KB |
Output is correct |
48 |
Correct |
551 ms |
18656 KB |
Output is correct |
49 |
Correct |
1573 ms |
87796 KB |
Output is correct |
50 |
Correct |
1385 ms |
87952 KB |
Output is correct |
51 |
Correct |
1602 ms |
87748 KB |
Output is correct |
52 |
Correct |
1763 ms |
87812 KB |
Output is correct |
53 |
Correct |
1439 ms |
87740 KB |
Output is correct |
54 |
Correct |
1501 ms |
87716 KB |
Output is correct |
55 |
Correct |
1416 ms |
87760 KB |
Output is correct |
56 |
Correct |
600 ms |
17992 KB |
Output is correct |
57 |
Correct |
768 ms |
18068 KB |
Output is correct |
58 |
Correct |
795 ms |
18500 KB |
Output is correct |
59 |
Correct |
1884 ms |
75952 KB |
Output is correct |
60 |
Correct |
2864 ms |
75944 KB |
Output is correct |
61 |
Correct |
1692 ms |
92604 KB |
Output is correct |
62 |
Correct |
1455 ms |
98296 KB |
Output is correct |
63 |
Correct |
2440 ms |
97112 KB |
Output is correct |
64 |
Correct |
1834 ms |
93656 KB |
Output is correct |
65 |
Correct |
1669 ms |
92668 KB |
Output is correct |
66 |
Correct |
2055 ms |
92896 KB |
Output is correct |
67 |
Correct |
1903 ms |
97252 KB |
Output is correct |
68 |
Correct |
1350 ms |
106808 KB |
Output is correct |
69 |
Correct |
2495 ms |
115904 KB |
Output is correct |