# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
580552 |
2022-06-21T12:26:52 Z |
Vanilla |
Seats (IOI18_seats) |
C++17 |
|
4000 ms |
59456 KB |
#include <bits/stdc++.h>
#include "seats.h"
typedef long long int64;
using namespace std;
vector<int> r,c;
const int maxn = 1e6 + 2;
int ll [maxn], rr[maxn], uu[maxn], dd[maxn], rs[maxn];
int n = 0, m = 0;
int query (int x) {
if (x == 0) return 1;
int r = 1;
for (; x >= 1; x-=x & -x) r+=rs[x];
return r;
}
void upd (int x, int d) {
for (; x < maxn; x+=x & -x) rs[x]+=d;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
r = R, c = C, n = H, m = W;
ll[0] = c[0], rr[0] = c[0], uu[0] = r[0], dd[0] = r[0];
for (int i = 1; i < n * m; i++){
ll[i] = min(ll[i-1], c[i]);
rr[i] = max(rr[i-1], c[i]);
uu[i] = min(uu[i-1], r[i]);
dd[i] = max(dd[i-1], r[i]);
// cout << i << " " << ll << " " << rr << " " << uu << " " << dd << "\n";
if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) == i + 1) upd(i, 1);
}
}
int swap_seats(int a, int b) {
swap(r[a], r[b]);
swap(c[a], c[b]);
if (a > b) swap(a,b);
if (a == 0) ll[0] = c[0], rr[0] = c[0], uu[0] = r[0], dd[0] = r[0];
for (int i = max(a, 1); i <= b; i++){
if (i == 0) continue;
ll[i] = min(ll[i-1], c[i]);
rr[i] = max(rr[i-1], c[i]);
uu[i] = min(uu[i-1], r[i]);
dd[i] = max(dd[i-1], r[i]);
// cout << i << " " << ll << " " << rr << " " << uu << " " << dd << "\n";
// if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) == i + 1) cout << i << " ";
if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) == i + 1 && query(i) - query(i - 1) != 1) upd(i, 1);
if ((rr[i] - ll[i] + 1) * (dd[i] - uu[i] + 1) != i + 1 && query(i) - query(i - 1) == 1) upd(i, -1);
}
return query(maxn - 1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
4 ms |
480 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
8 ms |
452 KB |
Output is correct |
6 |
Correct |
4 ms |
468 KB |
Output is correct |
7 |
Correct |
3 ms |
468 KB |
Output is correct |
8 |
Correct |
3 ms |
468 KB |
Output is correct |
9 |
Correct |
3 ms |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
468 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
12 |
Correct |
6 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
4 ms |
480 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
8 ms |
452 KB |
Output is correct |
6 |
Correct |
4 ms |
468 KB |
Output is correct |
7 |
Correct |
3 ms |
468 KB |
Output is correct |
8 |
Correct |
3 ms |
468 KB |
Output is correct |
9 |
Correct |
3 ms |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
468 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
12 |
Correct |
6 ms |
468 KB |
Output is correct |
13 |
Correct |
259 ms |
816 KB |
Output is correct |
14 |
Correct |
243 ms |
784 KB |
Output is correct |
15 |
Correct |
251 ms |
792 KB |
Output is correct |
16 |
Correct |
623 ms |
816 KB |
Output is correct |
17 |
Correct |
241 ms |
848 KB |
Output is correct |
18 |
Correct |
262 ms |
800 KB |
Output is correct |
19 |
Correct |
306 ms |
820 KB |
Output is correct |
20 |
Correct |
477 ms |
816 KB |
Output is correct |
21 |
Correct |
459 ms |
820 KB |
Output is correct |
22 |
Correct |
409 ms |
816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4066 ms |
39392 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
856 KB |
Output is correct |
2 |
Correct |
516 ms |
3924 KB |
Output is correct |
3 |
Correct |
869 ms |
42316 KB |
Output is correct |
4 |
Correct |
911 ms |
55356 KB |
Output is correct |
5 |
Correct |
1256 ms |
59340 KB |
Output is correct |
6 |
Correct |
877 ms |
55360 KB |
Output is correct |
7 |
Correct |
906 ms |
59340 KB |
Output is correct |
8 |
Correct |
886 ms |
55484 KB |
Output is correct |
9 |
Correct |
906 ms |
56756 KB |
Output is correct |
10 |
Correct |
878 ms |
55512 KB |
Output is correct |
11 |
Correct |
958 ms |
59456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
1444 KB |
Output is correct |
2 |
Correct |
18 ms |
1440 KB |
Output is correct |
3 |
Correct |
54 ms |
1400 KB |
Output is correct |
4 |
Correct |
382 ms |
1452 KB |
Output is correct |
5 |
Correct |
2390 ms |
1720 KB |
Output is correct |
6 |
Execution timed out |
4069 ms |
43708 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
4 ms |
480 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
8 ms |
452 KB |
Output is correct |
6 |
Correct |
4 ms |
468 KB |
Output is correct |
7 |
Correct |
3 ms |
468 KB |
Output is correct |
8 |
Correct |
3 ms |
468 KB |
Output is correct |
9 |
Correct |
3 ms |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
468 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
12 |
Correct |
6 ms |
468 KB |
Output is correct |
13 |
Correct |
259 ms |
816 KB |
Output is correct |
14 |
Correct |
243 ms |
784 KB |
Output is correct |
15 |
Correct |
251 ms |
792 KB |
Output is correct |
16 |
Correct |
623 ms |
816 KB |
Output is correct |
17 |
Correct |
241 ms |
848 KB |
Output is correct |
18 |
Correct |
262 ms |
800 KB |
Output is correct |
19 |
Correct |
306 ms |
820 KB |
Output is correct |
20 |
Correct |
477 ms |
816 KB |
Output is correct |
21 |
Correct |
459 ms |
820 KB |
Output is correct |
22 |
Correct |
409 ms |
816 KB |
Output is correct |
23 |
Execution timed out |
4066 ms |
39392 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |