# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
891276 |
2023-12-22T16:02:02 Z |
vjudge1 |
Seats (IOI18_seats) |
C++17 |
|
4000 ms |
86588 KB |
#include "seats.h"
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
struct AINT {
int n;
vi mi, ma;
AINT(int N = 0) : n(N), mi(4 * N), ma(4 * N) {}
void init(int N) {
n = N;
mi.assign(4 * N, 0);
ma.assign(4 * N, 0);
}
void update(int p, int v) { update(p, v, 1, 0, n - 1); }
void update(int p, int v, int u, int s, int d) {
if(d < p || p < s) return;
if(s == d) {
mi[u] = ma[u] = v;
return;
}
update(p, v, u << 1, s, (s + d) >> 1);
update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
mi[u] = min(mi[u << 1], mi[u << 1 | 1]);
ma[u] = max(ma[u << 1], ma[u << 1 | 1]);
}
ii query(int l, int r) { return query(l, r, 1, 0, n - 1); }
ii query(int l, int r, int u, int s, int d) {
if( d < l || r < s ) return {1e9, 0};
if(l <= s && d <= r)
return make_pair(mi[u], ma[u]);
auto [mi1, ma1] = query(l, r, u << 1, s, (s + d) >> 1);
auto [mi2, ma2] = query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
return make_pair(min(mi1, mi2), max(ma1, ma2));
}
};
vi r, c;
int reg = 0;
int tip = 0;
AINT AR, AC;
int h, w;
void give_initial_chart(int H, int W, vi R, vi C) {
h = H;
w = W;
r = R;
c = C;
AR.init(H * W);
AC.init(H * W);
for(int i = 0; i < H * W; ++i) {
AR.update(i, R[i]);
AC.update(i, C[i]);
}
}
bool ok(int l, int c) {
auto [mir, mar] = AR.query(0, l * c - 1);
auto [mic, mac] = AC.query(0, l * c - 1);
return (l * c) == ((mar - mir + 1) * (mac - mic + 1));
}
int swap_seats(int a, int b) {
swap(r[a], r[b]);
swap(c[a], c[b]);
AR.update(a, r[a]);
AR.update(b, r[b]);
AC.update(a, c[a]);
AC.update(b, c[b]);
int hc = 1, wc = 1, re = 1;
while(hc < h || wc < w) {
int facut = 0;
for(int delta = 1;; ++delta) {
int hh = hc + delta;
int ww = wc + delta;
if(hh > h && ww > w) break;
if(hh <= h && ok(hh, wc)) {
hc = hh;
++re;
facut = 1;
break;
}
if(ww <= w && ok(hc, ww)) {
wc = ww;
++re;
facut = 1;
break;
}
}
if(!facut) {
if(hc < h)
++hc;
else
++wc;
}
}
return re;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
348 KB |
Output is correct |
2 |
Incorrect |
6 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
348 KB |
Output is correct |
2 |
Incorrect |
6 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4017 ms |
86588 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4062 ms |
1116 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
1496 KB |
Output is correct |
2 |
Correct |
28 ms |
1492 KB |
Output is correct |
3 |
Correct |
431 ms |
1256 KB |
Output is correct |
4 |
Execution timed out |
4096 ms |
1180 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
348 KB |
Output is correct |
2 |
Incorrect |
6 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |