QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94863 | #5669. Traveling in Jade City | SEM_PRESSAO_pedroteosousa# | ML | 2ms | 5488kb | C++23 | 4.5kb | 2023-04-08 01:22:24 | 2023-04-08 01:22:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define all(v) v.begin(),v.end()
#define pb push_back
void dbg_out() {cerr << endl; }
template< typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
const int N = 2e6 + 10;
int n, k, m, q, c[N], x[N];
void solve () {
// u, 1, k, v
// u, k, 1, v
// u, v
// u, 1, v
// u, k, v
cin >> n >> k >> m >> q;
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 0; i <= m; i++) cin >> x[i];
int L = 0, M = 0, R = 0;
vector dist (n, vector<int> (n + m + 1));
{
int cur = 0;
for (int i = 1; i < k; i++) {
cur += c[i];
dist[0][i + 1] = cur;
}
R = cur;
}
{
int cur = 0;
for (int i = 0; i < m; i++) {
cur += x[i];
dist[0][n + i + 1] = cur;
}
M = cur + x[m];
}
{
int cur = 0;
for (int i = n; i >= k; i--) {
cur += c[i];
dist[0][i] = cur;
}
L = cur;
}
// vamos calcular agora a distancia para k
{
int cur = 0;
for (int i = k - 1; i >= 1; i--) {
cur += c[i];
dist[1][i] = cur;
}
}
{
int cur = 0;
for (int i = k + 1; i <= n; i++) {
cur += c[i - 1];
dist[1][i] = cur;
}
}
{
int cur = 0;
for (int i = n + m; i >= n + 1; i--) {
cur += x[i - n];
dist[1][i] = cur;
}
}
// dbg (L, M, R);
// for (int i = 1; i <= n + m; i++) cout << dist[0][i] << " ";
// cout << "\n";
// for (int i = 1; i <= n + m; i++) cout << dist[1][i] << " ";
// cout << "\n";
set<int> esq, meio, dir;
const int INF = 1e17;
while (q--) {
char op; cin >> op;
if (op == 'x') {
int j; cin >> j;
if (meio.find (j) != meio.end ()) meio.erase (j);
else meio.insert (j);
}
else if (op == 'c') {
int j; cin >> j;
if (j < k) {
if (dir.find (j) != dir.end ()) dir.erase (j);
else dir.insert (j);
}
else {
if (esq.find (j) != esq.end ()) esq.erase (j);
else esq.insert (j);
}
}
else {
auto find_path = [&] (int u, int pivot) -> bool {
// vamos tentar ir do u para pivot
if (u == pivot) return 1;
if (pivot == 1) {
if (u < k) return !dir.size () || *dir.begin () >= u;
else if (u <= n) return !esq.size () || *--esq.end () < u;
else return !meio.size () || *meio.begin () >= u - n;
}
else {
if (u < k) return !dir.size () || *--dir.end () < u;
else if (u <= n) return !esq.size () || *esq.begin () >= u;
else return !meio.size () || *--meio.end () < u - n;
}
};
int u, v; cin >> u >> v;
if (u > v) swap (u, v);
int ans = INF;
// vamos tentar ir direto
if (1 < u && v < k) {
// se estao na direita!
auto it = dir.lower_bound (u);
if (it == dir.end () || *it >= v) ans = min (ans, dist[0][v] - dist[0][u]);
}
if (k < u && v <= n) {
// se estao na esquerda!
auto it = esq.lower_bound (u);
if (it == esq.end () || *it >= v) ans = min (ans, dist[1][v] - dist[1][u]);
}
if (n + 1 <= u && v <= n + m) {
// se estao no meio
auto it = meio.lower_bound (u - n);
if (it == meio.end () || *it >= v) ans = min (ans, dist[0][v] - dist[0][u]);
}
// se consigo fazer u -> 1
if (u != k) {
int cur = 0;
if (find_path (u, 1)) {
cur += dist[0][u];
// tentamos ir direto para v
if (find_path (v, 1)) {
ans = min (ans, cur + dist[0][v]);
}
// tentamos ir para k
int bridge = INF;
if (!esq.size ()) bridge = min (bridge, L);
if (!dir.size ()) bridge = min (bridge, R);
if (!meio.size ()) bridge = min (bridge, M);
if (bridge != INF) {
cur += bridge;
if (find_path (v, k)) {
ans = min (ans, cur + dist[1][v]);
}
}
}
}
else {
int cur = 0;
if (find_path (u, k)) {
cur += dist[1][u];
// tentamos ir direto para v
if (find_path (v, k)) {
ans = min (ans, cur + dist[1][v]);
}
// tentamos ir para k
int bridge = INF;
if (!esq.size ()) bridge = min (bridge, L);
if (!dir.size ()) bridge = min (bridge, R);
if (!meio.size ()) bridge = min (bridge, M);
if (bridge != INF) {
cur += bridge;
if (find_path (v, 1)) {
ans = min (ans, cur + dist[0][v]);
}
}
}
}
if (ans == INF) cout << "impossible\n";
else cout << ans << "\n";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5464kb
input:
4 3 1 9 2 3 8 4 1 1 q 3 4 x 0 q 3 4 c 3 q 3 4 c 1 q 3 4 x 0 q 3 4
output:
6 8 9 impossible 6
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 5488kb
input:
4 3 1 9 2 3 8 4 1 1 q 3 4 x 0 q 3 4 c 3 q 3 4 c 1 q 3 4 x 0 q 3 4
output:
6 8 9 impossible 6
result:
ok 5 lines
Test #3:
score: -100
Memory Limit Exceeded
input:
1000000 999999 1000000 1000000 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 2...