# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
835111 |
2023-08-23T08:32:29 Z |
Johann |
Seats (IOI18_seats) |
C++14 |
|
4000 ms |
72596 KB |
#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int H, W;
std::vector<int> R, C;
struct segtree
{
int size;
vi mini, maxi;
void init(vi &A)
{
size = 1;
while (size < sz(A))
size *= 2;
mini.assign(2 * size, INT_MAX);
maxi.assign(2 * size, INT_MIN);
for (int i = 0; i < sz(A); ++i)
mini[i + size] = maxi[i + size] = A[i];
for (int i = sz(A) - 1; i > 0; --i)
maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]), mini[i] = min(mini[2 * i], mini[2 * i + 1]);
}
void set(int i, int v)
{
i += size;
mini[i] = maxi[i] = v;
while (i >>= 1 > 0)
maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]), mini[i] = min(mini[2 * i], mini[2 * i + 1]);
}
pii query(int l, int r) { return query(l, r, 1, 0, size); }
pii query(int l, int r, int x, int lx, int rx)
{
if (l <= lx && rx <= r)
return {mini[x], maxi[x]};
if (r <= lx || rx <= l)
return {INT_MAX, INT_MIN};
int m = (lx + rx) / 2;
int mini1, mini2, maxi1, maxi2;
tie(mini1, maxi1) = query(l, r, 2 * x, lx, m);
tie(mini2, maxi2) = query(l, r, 2 * x + 1, m, rx);
return {min(mini1, mini2), max(maxi1, maxi2)};
}
};
segtree segR;
segtree segC;
void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C)
{
H = _H, W = _W;
R = _R, C = _C;
segR.init(R), segC.init(C);
}
int swap_seats(int a, int b)
{
swap(R[a], R[b]), swap(C[a], C[b]);
segR.set(a, R[a]), segC.set(a, C[a]);
segR.set(b, R[b]), segC.set(b, C[b]);
int rmax = R[0], rmin = R[0];
int cmax = C[0], cmin = C[0];
int ans = 0;
int k = 0;
while (k < H * W)
{
tie(rmin, rmax) = segR.query(0, k + 1);
tie(cmin, cmax) = segC.query(0, k + 1);
int area = (rmax - rmin + 1) * (cmax - cmin + 1);
if (area == k + 1)
++ans, ++k;
else
k = area - 1;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4030 ms |
212 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4030 ms |
212 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
177 ms |
56640 KB |
Output is correct |
2 |
Execution timed out |
4038 ms |
72596 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4048 ms |
1108 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
1360 KB |
Output is correct |
2 |
Execution timed out |
4074 ms |
596 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4030 ms |
212 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |