#pragma GCC target("avx,avx2,sse,sse2")
#pragma GCC optimize("Ofast")
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < b; ++i)
struct T {
int mn;
int cnt;
static T mrg(T a, T b){
int mn = min(a.mn, b.mn);
int cnt = (a.mn == mn ? a.cnt : 0) + (b.mn == mn ? b.cnt : 0);
return T{mn,cnt};
}
static T small() { return T{2123123, 0}; }
static T def() { return T{0, 1}; }
};
#define cc(x) complex<int>(x.mn, x.cnt)
struct ST {
int n;
vector<T> v;
vector<int> delta;
void init(int m) {
n = 1;
while(n < m) n *= 2;
v.resize(2*n, T::small());
delta.resize(2*n, 0);
rep(i,0,m) v[i+n] = T::def();
for(int i = n-1; i; --i) v[i] = T::mrg(v[2*i], v[2*i+1]);
}
void push(int t){
if(delta[t] != 0) {
if(t < n) {
delta[2*t+0] += delta[t];
delta[2*t+1] += delta[t];
}
v[t].mn += delta[t];
delta[t] = 0;
}
}
const T& query() {
push(1);
return v[1];
}
const T& upd(int t, int L, int R, int l, int r, int d) {
push(t);
if(l <= L && R <= r) {
delta[t] += d;
push(t);
return v[t];
}
if(r <= L || R <= l) return v[t];
int M = (L+R)/2;
return v[t] = T::mrg(upd(2*t, L, M, l, r, d), upd(2*t+1, M, R, l, r, d));
}
void update(int l, int r, int d){
r = min(n,r);
upd(1, 0, n, l, r, d);
}
};
struct HW {
int n;
vector<int> r, c;
ST st;
int H, W;
int cnt;
bool ini;
set<int> active;
vector<vector<int> > board;
void init(vector<int> r_, vector<int> c_, int H_, int W_){
H = H_;
W = W_;
r = r_;
c = c_;
n = r.size();
st.init(n);
board.resize(H, vector<int>(W));
rep(i,0,n) board[r[i]][c[i]] = i;
rep(x,-1,H) rep(y,-1,W) sqr(x,y,1);
}
int gt(int a, int b){
if(a < 0 || b < 0 || a >= H || b >= W) return 2123123;
else return board[a][b];
}
void sqr(int x, int y, int delta) {
vector<int> all{gt(x,y),gt(x+1,y),gt(x,y+1),gt(x+1,y+1)};
sort(all.begin(),all.end());
vector<pair<int,int> > inv;
int kk = min(gt(x+1,y),gt(x,y+1));
int k0 = gt(x+1,y+1);
if(k0 < kk) st.update(k0, kk, delta);
if(all[2] < n-1) st.update(all[2], all[3], delta);
}
void update(int x, int y, int nw) {
for(int delta : {-1,1}) {
sqr(x-1,y-1,delta);
sqr(x,y-1,delta);
sqr(x-1,y,delta);
sqr(x,y,delta);
board[x][y] = nw;
}
}
int calc() {
T t = st.query();
return t.cnt;
}
int swap(int a, int b){
if(a>b) std::swap(a,b);
update(r[a], c[a], b);
update(r[b], c[b], a);
std::swap(r[a],r[b]);
std::swap(c[a],c[b]);
return calc();
}
} hw;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
hw.init(R,C,H,W);
}
int swap_seats(int a, int b) {
return hw.swap(a,b);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
376 KB |
Output is correct |
2 |
Correct |
26 ms |
500 KB |
Output is correct |
3 |
Correct |
38 ms |
500 KB |
Output is correct |
4 |
Correct |
17 ms |
552 KB |
Output is correct |
5 |
Correct |
15 ms |
612 KB |
Output is correct |
6 |
Correct |
30 ms |
612 KB |
Output is correct |
7 |
Correct |
35 ms |
612 KB |
Output is correct |
8 |
Correct |
33 ms |
616 KB |
Output is correct |
9 |
Correct |
29 ms |
632 KB |
Output is correct |
10 |
Correct |
32 ms |
632 KB |
Output is correct |
11 |
Correct |
29 ms |
692 KB |
Output is correct |
12 |
Correct |
14 ms |
748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
376 KB |
Output is correct |
2 |
Correct |
26 ms |
500 KB |
Output is correct |
3 |
Correct |
38 ms |
500 KB |
Output is correct |
4 |
Correct |
17 ms |
552 KB |
Output is correct |
5 |
Correct |
15 ms |
612 KB |
Output is correct |
6 |
Correct |
30 ms |
612 KB |
Output is correct |
7 |
Correct |
35 ms |
612 KB |
Output is correct |
8 |
Correct |
33 ms |
616 KB |
Output is correct |
9 |
Correct |
29 ms |
632 KB |
Output is correct |
10 |
Correct |
32 ms |
632 KB |
Output is correct |
11 |
Correct |
29 ms |
692 KB |
Output is correct |
12 |
Correct |
14 ms |
748 KB |
Output is correct |
13 |
Correct |
69 ms |
1456 KB |
Output is correct |
14 |
Correct |
86 ms |
1464 KB |
Output is correct |
15 |
Correct |
32 ms |
1464 KB |
Output is correct |
16 |
Correct |
23 ms |
1960 KB |
Output is correct |
17 |
Correct |
57 ms |
1960 KB |
Output is correct |
18 |
Correct |
52 ms |
1960 KB |
Output is correct |
19 |
Correct |
49 ms |
1960 KB |
Output is correct |
20 |
Correct |
43 ms |
1960 KB |
Output is correct |
21 |
Correct |
25 ms |
1960 KB |
Output is correct |
22 |
Correct |
25 ms |
1960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2039 ms |
60592 KB |
Output is correct |
2 |
Correct |
1095 ms |
60704 KB |
Output is correct |
3 |
Correct |
1156 ms |
60704 KB |
Output is correct |
4 |
Correct |
837 ms |
60704 KB |
Output is correct |
5 |
Correct |
860 ms |
60704 KB |
Output is correct |
6 |
Correct |
1162 ms |
60704 KB |
Output is correct |
7 |
Correct |
1046 ms |
60704 KB |
Output is correct |
8 |
Correct |
973 ms |
60704 KB |
Output is correct |
9 |
Correct |
1187 ms |
60716 KB |
Output is correct |
10 |
Correct |
989 ms |
60716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
70 ms |
60716 KB |
Output is correct |
2 |
Correct |
162 ms |
60716 KB |
Output is correct |
3 |
Correct |
935 ms |
60716 KB |
Output is correct |
4 |
Correct |
2100 ms |
60716 KB |
Output is correct |
5 |
Correct |
798 ms |
64444 KB |
Output is correct |
6 |
Correct |
1527 ms |
111440 KB |
Output is correct |
7 |
Correct |
751 ms |
111440 KB |
Output is correct |
8 |
Correct |
1273 ms |
111440 KB |
Output is correct |
9 |
Correct |
917 ms |
111440 KB |
Output is correct |
10 |
Correct |
868 ms |
111440 KB |
Output is correct |
11 |
Correct |
786 ms |
111440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
97 ms |
111440 KB |
Output is correct |
2 |
Correct |
121 ms |
111440 KB |
Output is correct |
3 |
Correct |
135 ms |
111440 KB |
Output is correct |
4 |
Correct |
168 ms |
111440 KB |
Output is correct |
5 |
Correct |
209 ms |
111440 KB |
Output is correct |
6 |
Correct |
980 ms |
111440 KB |
Output is correct |
7 |
Correct |
1162 ms |
111440 KB |
Output is correct |
8 |
Correct |
1096 ms |
111440 KB |
Output is correct |
9 |
Correct |
1734 ms |
111440 KB |
Output is correct |
10 |
Correct |
875 ms |
111440 KB |
Output is correct |
11 |
Correct |
946 ms |
111440 KB |
Output is correct |
12 |
Correct |
713 ms |
111440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
376 KB |
Output is correct |
2 |
Correct |
26 ms |
500 KB |
Output is correct |
3 |
Correct |
38 ms |
500 KB |
Output is correct |
4 |
Correct |
17 ms |
552 KB |
Output is correct |
5 |
Correct |
15 ms |
612 KB |
Output is correct |
6 |
Correct |
30 ms |
612 KB |
Output is correct |
7 |
Correct |
35 ms |
612 KB |
Output is correct |
8 |
Correct |
33 ms |
616 KB |
Output is correct |
9 |
Correct |
29 ms |
632 KB |
Output is correct |
10 |
Correct |
32 ms |
632 KB |
Output is correct |
11 |
Correct |
29 ms |
692 KB |
Output is correct |
12 |
Correct |
14 ms |
748 KB |
Output is correct |
13 |
Correct |
69 ms |
1456 KB |
Output is correct |
14 |
Correct |
86 ms |
1464 KB |
Output is correct |
15 |
Correct |
32 ms |
1464 KB |
Output is correct |
16 |
Correct |
23 ms |
1960 KB |
Output is correct |
17 |
Correct |
57 ms |
1960 KB |
Output is correct |
18 |
Correct |
52 ms |
1960 KB |
Output is correct |
19 |
Correct |
49 ms |
1960 KB |
Output is correct |
20 |
Correct |
43 ms |
1960 KB |
Output is correct |
21 |
Correct |
25 ms |
1960 KB |
Output is correct |
22 |
Correct |
25 ms |
1960 KB |
Output is correct |
23 |
Correct |
2039 ms |
60592 KB |
Output is correct |
24 |
Correct |
1095 ms |
60704 KB |
Output is correct |
25 |
Correct |
1156 ms |
60704 KB |
Output is correct |
26 |
Correct |
837 ms |
60704 KB |
Output is correct |
27 |
Correct |
860 ms |
60704 KB |
Output is correct |
28 |
Correct |
1162 ms |
60704 KB |
Output is correct |
29 |
Correct |
1046 ms |
60704 KB |
Output is correct |
30 |
Correct |
973 ms |
60704 KB |
Output is correct |
31 |
Correct |
1187 ms |
60716 KB |
Output is correct |
32 |
Correct |
989 ms |
60716 KB |
Output is correct |
33 |
Correct |
70 ms |
60716 KB |
Output is correct |
34 |
Correct |
162 ms |
60716 KB |
Output is correct |
35 |
Correct |
935 ms |
60716 KB |
Output is correct |
36 |
Correct |
2100 ms |
60716 KB |
Output is correct |
37 |
Correct |
798 ms |
64444 KB |
Output is correct |
38 |
Correct |
1527 ms |
111440 KB |
Output is correct |
39 |
Correct |
751 ms |
111440 KB |
Output is correct |
40 |
Correct |
1273 ms |
111440 KB |
Output is correct |
41 |
Correct |
917 ms |
111440 KB |
Output is correct |
42 |
Correct |
868 ms |
111440 KB |
Output is correct |
43 |
Correct |
786 ms |
111440 KB |
Output is correct |
44 |
Correct |
97 ms |
111440 KB |
Output is correct |
45 |
Correct |
121 ms |
111440 KB |
Output is correct |
46 |
Correct |
135 ms |
111440 KB |
Output is correct |
47 |
Correct |
168 ms |
111440 KB |
Output is correct |
48 |
Correct |
209 ms |
111440 KB |
Output is correct |
49 |
Correct |
980 ms |
111440 KB |
Output is correct |
50 |
Correct |
1162 ms |
111440 KB |
Output is correct |
51 |
Correct |
1096 ms |
111440 KB |
Output is correct |
52 |
Correct |
1734 ms |
111440 KB |
Output is correct |
53 |
Correct |
875 ms |
111440 KB |
Output is correct |
54 |
Correct |
946 ms |
111440 KB |
Output is correct |
55 |
Correct |
713 ms |
111440 KB |
Output is correct |
56 |
Correct |
200 ms |
111440 KB |
Output is correct |
57 |
Correct |
373 ms |
111440 KB |
Output is correct |
58 |
Correct |
505 ms |
111440 KB |
Output is correct |
59 |
Correct |
1944 ms |
111440 KB |
Output is correct |
60 |
Correct |
3210 ms |
111440 KB |
Output is correct |
61 |
Correct |
1680 ms |
111440 KB |
Output is correct |
62 |
Correct |
1167 ms |
111440 KB |
Output is correct |
63 |
Correct |
2833 ms |
111440 KB |
Output is correct |
64 |
Correct |
1975 ms |
111440 KB |
Output is correct |
65 |
Correct |
1531 ms |
111440 KB |
Output is correct |
66 |
Correct |
1927 ms |
111440 KB |
Output is correct |
67 |
Correct |
1769 ms |
111440 KB |
Output is correct |
68 |
Correct |
1262 ms |
111440 KB |
Output is correct |
69 |
Correct |
2613 ms |
111440 KB |
Output is correct |