# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
764419 |
2023-06-23T11:42:41 Z |
khshg |
Seats (IOI18_seats) |
C++14 |
|
4000 ms |
35556 KB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
#define mp make_pair
#define ff first
#define ss second
#define ar array
template<class T> using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<ld>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
#define sz(x) (int)((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define trav(a, x) for(auto& a : x)
template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); }
template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); }
int N, M;
vi R, C;
int Lf[1000000], Rf[1000000], Ls[1000000], Rs[1000000], ans;
void dodo() {
ans = 1;
Lf[0] = R[0]; Rf[0] = R[0]; Ls[0] = C[0]; Rs[0] = C[0];
FOR(i, 1, N * M) {
Lf[i] = min(Lf[i - 1], R[i]);
Rf[i] = max(Rf[i - 1], R[i]);
Ls[i] = min(Ls[i - 1], C[i]);
Rs[i] = max(Rs[i - 1], C[i]);
if(i + 1 == (Rf[i] - Lf[i] + 1) * (Rs[i] - Ls[i] + 1)) ++ans;
}
}
void give_initial_chart(int _N, int _M, vi _R, vi _C) {
swap(N, _N);
swap(M, _M);
swap(R, _R);
swap(C, _C);
dodo();
}
int swap_seats(int A, int B) {
if(A > B) swap(A, B);
swap(R[A], R[B]);
swap(C[A], C[B]);
if(!A) {
Lf[0] = R[0]; Rf[0] = R[0]; Ls[0] = C[0]; Rs[0] = C[0];
++A;
}
FOR(i, A, B + 1) {
if(i + 1 == (Rf[i] - Lf[i] + 1) * (Rs[i] - Ls[i] + 1)) --ans;
Lf[i] = min(Lf[i - 1], R[i]);
Rf[i] = max(Rf[i - 1], R[i]);
Ls[i] = min(Ls[i - 1], C[i]);
Rs[i] = max(Rs[i - 1], C[i]);
if(i + 1 == (Rf[i] - Lf[i] + 1) * (Rs[i] - Ls[i] + 1)) ++ans;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
396 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
396 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
66 ms |
716 KB |
Output is correct |
14 |
Correct |
66 ms |
696 KB |
Output is correct |
15 |
Correct |
78 ms |
688 KB |
Output is correct |
16 |
Correct |
68 ms |
692 KB |
Output is correct |
17 |
Correct |
65 ms |
708 KB |
Output is correct |
18 |
Correct |
70 ms |
684 KB |
Output is correct |
19 |
Correct |
66 ms |
684 KB |
Output is correct |
20 |
Correct |
66 ms |
696 KB |
Output is correct |
21 |
Correct |
67 ms |
688 KB |
Output is correct |
22 |
Correct |
66 ms |
684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4054 ms |
31676 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
720 KB |
Output is correct |
2 |
Correct |
109 ms |
3196 KB |
Output is correct |
3 |
Correct |
255 ms |
31672 KB |
Output is correct |
4 |
Correct |
270 ms |
35556 KB |
Output is correct |
5 |
Correct |
276 ms |
35452 KB |
Output is correct |
6 |
Correct |
263 ms |
35496 KB |
Output is correct |
7 |
Correct |
266 ms |
35516 KB |
Output is correct |
8 |
Correct |
273 ms |
35540 KB |
Output is correct |
9 |
Correct |
276 ms |
35508 KB |
Output is correct |
10 |
Correct |
268 ms |
35492 KB |
Output is correct |
11 |
Correct |
273 ms |
35540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
1356 KB |
Output is correct |
2 |
Correct |
13 ms |
1360 KB |
Output is correct |
3 |
Correct |
18 ms |
1348 KB |
Output is correct |
4 |
Correct |
108 ms |
1304 KB |
Output is correct |
5 |
Correct |
673 ms |
1600 KB |
Output is correct |
6 |
Execution timed out |
4062 ms |
31936 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
396 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
340 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
66 ms |
716 KB |
Output is correct |
14 |
Correct |
66 ms |
696 KB |
Output is correct |
15 |
Correct |
78 ms |
688 KB |
Output is correct |
16 |
Correct |
68 ms |
692 KB |
Output is correct |
17 |
Correct |
65 ms |
708 KB |
Output is correct |
18 |
Correct |
70 ms |
684 KB |
Output is correct |
19 |
Correct |
66 ms |
684 KB |
Output is correct |
20 |
Correct |
66 ms |
696 KB |
Output is correct |
21 |
Correct |
67 ms |
688 KB |
Output is correct |
22 |
Correct |
66 ms |
684 KB |
Output is correct |
23 |
Execution timed out |
4054 ms |
31676 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |