# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
943771 |
2024-03-11T21:03:22 Z |
Lobo |
Seats (IOI18_seats) |
C++17 |
|
3129 ms |
157520 KB |
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e6+10;
const int B = 1000;
int n, m, col[maxn], row[maxn];
vector<vector<int>> grid;
int trmn[4*maxn], trq[4*maxn], lz[4*maxn];
void build(int no, int l, int r) {
trq[no] = r-l+1;
trmn[no] = 0;
if(l == r) return;
int lc=2*no,rc=2*no+1,mid=(l+r)/2;
build(lc,l,mid);
build(rc,mid+1,r);
}
void flush(int no, int l, int r) {
trmn[no]+= lz[no];
if(l != r) {
int lc=2*no,rc=2*no+1;
lz[lc]+= lz[no];
lz[rc]+= lz[no];
}
lz[no] = 0;
}
void upd(int no, int l, int r, int ll, int rr, int val) {
flush(no,l,r);
if(l > rr or r < ll) return;
if(l >= ll && r <= rr) {
lz[no] = val;
flush(no,l,r);
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)/2;
upd(lc,l,mid,ll,rr,val);
upd(rc,mid+1,r,ll,rr,val);
trmn[no] = min(trmn[lc],trmn[rc]);
trq[no] = 0;
if(trmn[no] == trmn[lc]) trq[no]+= trq[lc];
if(trmn[no] == trmn[rc]) trq[no]+= trq[rc];
}
void construct(int i, int j, int dx) {
vector<int> times;
for(int di = 0; di <= 1; di++) {
for(int dj = 0; dj <= 1; dj++) {
if(i+di >= 0 && i+di < n && j+dj >= 0 && j+dj < m) {
times.pb(grid[i+di][j+dj]);
}
}
}
sort(all(times));
for(int i = 0; i < (int) times.size(); i++) {
int tl = times[i];
int tr;
if(i+1 < (int) times.size()) tr = times[i+1]-1;
else tr = n*m-1;
if(i+1 == 1) {
upd(1,0,n*m-1,tl,tr,+1*dx);
}
if(i+1 == 3) upd(1,0,n*m-1,tl,tr,+5*dx);
}
}
void give_initial_chart(int32_t H, int32_t W, std::vector<int32_t> R, std::vector<int32_t> C) {
n = H;
m = W;
grid.resize(n,vector<int>(m));
for(int i = 0; i < n*m; i++) {
col[i] = C[i];
row[i] = R[i];
grid[row[i]][col[i]] = i;
}
build(1,0,n*m-1);
for(int i = -1; i < n; i++) {
for(int j = -1; j < m; j++) {
construct(i,j,1);
}
}
}
int32_t swap_seats(int32_t a, int32_t b) {
int i,j;
set<pair<int,int>> st;
i = row[a];
j = col[a];
for(int di = -1; di <= 0; di++) {
for(int dj = -1; dj <= 0; dj++) {
if(i+di >= -1 && i+di < n && j+dj >= -1 && j+dj < m) {
st.insert(mp(i+di,j+dj));
}
}
}
i = row[b];
j = col[b];
for(int di = -1; di <= 0; di++) {
for(int dj = -1; dj <= 0; dj++) {
if(i+di >= -1 && i+di < n && j+dj >= -1 && j+dj < m) {
st.insert(mp(i+di,j+dj));
}
}
}
for(auto x : st) {
construct(x.fr,x.sc,-1);
}
swap(col[a],col[b]);
swap(row[a],row[b]);
grid[row[a]][col[a]] = a;
grid[row[b]][col[b]] = b;
for(auto x : st) {
construct(x.fr,x.sc,+1);
}
return trq[1];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
8796 KB |
Output is correct |
2 |
Correct |
25 ms |
8796 KB |
Output is correct |
3 |
Correct |
35 ms |
8788 KB |
Output is correct |
4 |
Correct |
25 ms |
8792 KB |
Output is correct |
5 |
Correct |
22 ms |
8784 KB |
Output is correct |
6 |
Correct |
33 ms |
8772 KB |
Output is correct |
7 |
Correct |
32 ms |
8792 KB |
Output is correct |
8 |
Correct |
31 ms |
8740 KB |
Output is correct |
9 |
Correct |
30 ms |
8796 KB |
Output is correct |
10 |
Correct |
32 ms |
8784 KB |
Output is correct |
11 |
Correct |
30 ms |
8796 KB |
Output is correct |
12 |
Correct |
21 ms |
8788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
8796 KB |
Output is correct |
2 |
Correct |
25 ms |
8796 KB |
Output is correct |
3 |
Correct |
35 ms |
8788 KB |
Output is correct |
4 |
Correct |
25 ms |
8792 KB |
Output is correct |
5 |
Correct |
22 ms |
8784 KB |
Output is correct |
6 |
Correct |
33 ms |
8772 KB |
Output is correct |
7 |
Correct |
32 ms |
8792 KB |
Output is correct |
8 |
Correct |
31 ms |
8740 KB |
Output is correct |
9 |
Correct |
30 ms |
8796 KB |
Output is correct |
10 |
Correct |
32 ms |
8784 KB |
Output is correct |
11 |
Correct |
30 ms |
8796 KB |
Output is correct |
12 |
Correct |
21 ms |
8788 KB |
Output is correct |
13 |
Correct |
67 ms |
11296 KB |
Output is correct |
14 |
Correct |
74 ms |
11300 KB |
Output is correct |
15 |
Correct |
46 ms |
11376 KB |
Output is correct |
16 |
Correct |
35 ms |
11612 KB |
Output is correct |
17 |
Correct |
56 ms |
11356 KB |
Output is correct |
18 |
Correct |
55 ms |
11100 KB |
Output is correct |
19 |
Correct |
56 ms |
11352 KB |
Output is correct |
20 |
Correct |
46 ms |
11352 KB |
Output is correct |
21 |
Correct |
43 ms |
11376 KB |
Output is correct |
22 |
Correct |
36 ms |
11612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1795 ms |
106960 KB |
Output is correct |
2 |
Correct |
924 ms |
106888 KB |
Output is correct |
3 |
Correct |
867 ms |
110588 KB |
Output is correct |
4 |
Correct |
799 ms |
110540 KB |
Output is correct |
5 |
Correct |
837 ms |
110840 KB |
Output is correct |
6 |
Correct |
777 ms |
110572 KB |
Output is correct |
7 |
Correct |
830 ms |
110652 KB |
Output is correct |
8 |
Correct |
874 ms |
110596 KB |
Output is correct |
9 |
Correct |
873 ms |
110420 KB |
Output is correct |
10 |
Correct |
850 ms |
110520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
11304 KB |
Output is correct |
2 |
Correct |
137 ms |
20316 KB |
Output is correct |
3 |
Correct |
855 ms |
111068 KB |
Output is correct |
4 |
Correct |
1844 ms |
110588 KB |
Output is correct |
5 |
Correct |
772 ms |
110796 KB |
Output is correct |
6 |
Correct |
1743 ms |
157520 KB |
Output is correct |
7 |
Correct |
879 ms |
110564 KB |
Output is correct |
8 |
Correct |
915 ms |
110676 KB |
Output is correct |
9 |
Correct |
830 ms |
110932 KB |
Output is correct |
10 |
Correct |
865 ms |
114452 KB |
Output is correct |
11 |
Correct |
798 ms |
130136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
10188 KB |
Output is correct |
2 |
Correct |
140 ms |
10192 KB |
Output is correct |
3 |
Correct |
208 ms |
10224 KB |
Output is correct |
4 |
Correct |
241 ms |
10260 KB |
Output is correct |
5 |
Correct |
358 ms |
12752 KB |
Output is correct |
6 |
Correct |
1179 ms |
111308 KB |
Output is correct |
7 |
Correct |
1479 ms |
111564 KB |
Output is correct |
8 |
Correct |
1195 ms |
111704 KB |
Output is correct |
9 |
Correct |
2497 ms |
111516 KB |
Output is correct |
10 |
Correct |
1184 ms |
111464 KB |
Output is correct |
11 |
Correct |
1230 ms |
111608 KB |
Output is correct |
12 |
Correct |
1096 ms |
111308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
8796 KB |
Output is correct |
2 |
Correct |
25 ms |
8796 KB |
Output is correct |
3 |
Correct |
35 ms |
8788 KB |
Output is correct |
4 |
Correct |
25 ms |
8792 KB |
Output is correct |
5 |
Correct |
22 ms |
8784 KB |
Output is correct |
6 |
Correct |
33 ms |
8772 KB |
Output is correct |
7 |
Correct |
32 ms |
8792 KB |
Output is correct |
8 |
Correct |
31 ms |
8740 KB |
Output is correct |
9 |
Correct |
30 ms |
8796 KB |
Output is correct |
10 |
Correct |
32 ms |
8784 KB |
Output is correct |
11 |
Correct |
30 ms |
8796 KB |
Output is correct |
12 |
Correct |
21 ms |
8788 KB |
Output is correct |
13 |
Correct |
67 ms |
11296 KB |
Output is correct |
14 |
Correct |
74 ms |
11300 KB |
Output is correct |
15 |
Correct |
46 ms |
11376 KB |
Output is correct |
16 |
Correct |
35 ms |
11612 KB |
Output is correct |
17 |
Correct |
56 ms |
11356 KB |
Output is correct |
18 |
Correct |
55 ms |
11100 KB |
Output is correct |
19 |
Correct |
56 ms |
11352 KB |
Output is correct |
20 |
Correct |
46 ms |
11352 KB |
Output is correct |
21 |
Correct |
43 ms |
11376 KB |
Output is correct |
22 |
Correct |
36 ms |
11612 KB |
Output is correct |
23 |
Correct |
1795 ms |
106960 KB |
Output is correct |
24 |
Correct |
924 ms |
106888 KB |
Output is correct |
25 |
Correct |
867 ms |
110588 KB |
Output is correct |
26 |
Correct |
799 ms |
110540 KB |
Output is correct |
27 |
Correct |
837 ms |
110840 KB |
Output is correct |
28 |
Correct |
777 ms |
110572 KB |
Output is correct |
29 |
Correct |
830 ms |
110652 KB |
Output is correct |
30 |
Correct |
874 ms |
110596 KB |
Output is correct |
31 |
Correct |
873 ms |
110420 KB |
Output is correct |
32 |
Correct |
850 ms |
110520 KB |
Output is correct |
33 |
Correct |
67 ms |
11304 KB |
Output is correct |
34 |
Correct |
137 ms |
20316 KB |
Output is correct |
35 |
Correct |
855 ms |
111068 KB |
Output is correct |
36 |
Correct |
1844 ms |
110588 KB |
Output is correct |
37 |
Correct |
772 ms |
110796 KB |
Output is correct |
38 |
Correct |
1743 ms |
157520 KB |
Output is correct |
39 |
Correct |
879 ms |
110564 KB |
Output is correct |
40 |
Correct |
915 ms |
110676 KB |
Output is correct |
41 |
Correct |
830 ms |
110932 KB |
Output is correct |
42 |
Correct |
865 ms |
114452 KB |
Output is correct |
43 |
Correct |
798 ms |
130136 KB |
Output is correct |
44 |
Correct |
83 ms |
10188 KB |
Output is correct |
45 |
Correct |
140 ms |
10192 KB |
Output is correct |
46 |
Correct |
208 ms |
10224 KB |
Output is correct |
47 |
Correct |
241 ms |
10260 KB |
Output is correct |
48 |
Correct |
358 ms |
12752 KB |
Output is correct |
49 |
Correct |
1179 ms |
111308 KB |
Output is correct |
50 |
Correct |
1479 ms |
111564 KB |
Output is correct |
51 |
Correct |
1195 ms |
111704 KB |
Output is correct |
52 |
Correct |
2497 ms |
111516 KB |
Output is correct |
53 |
Correct |
1184 ms |
111464 KB |
Output is correct |
54 |
Correct |
1230 ms |
111608 KB |
Output is correct |
55 |
Correct |
1096 ms |
111308 KB |
Output is correct |
56 |
Correct |
161 ms |
10188 KB |
Output is correct |
57 |
Correct |
341 ms |
10188 KB |
Output is correct |
58 |
Correct |
510 ms |
12820 KB |
Output is correct |
59 |
Correct |
1637 ms |
111556 KB |
Output is correct |
60 |
Correct |
3001 ms |
111704 KB |
Output is correct |
61 |
Correct |
1517 ms |
111556 KB |
Output is correct |
62 |
Correct |
1261 ms |
111636 KB |
Output is correct |
63 |
Correct |
3129 ms |
111524 KB |
Output is correct |
64 |
Correct |
1785 ms |
111540 KB |
Output is correct |
65 |
Correct |
1685 ms |
111588 KB |
Output is correct |
66 |
Correct |
1782 ms |
111692 KB |
Output is correct |
67 |
Correct |
1738 ms |
115424 KB |
Output is correct |
68 |
Correct |
1365 ms |
121828 KB |
Output is correct |
69 |
Correct |
2565 ms |
131076 KB |
Output is correct |