QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#123379 | #5669. Traveling in Jade City | GenshinImpactsFault# | WA | 407ms | 34584kb | C++14 | 2.6kb | 2023-07-12 14:20:22 | 2023-07-12 14:20:22 |
Judging History
answer
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int N = 1000010;
const int INF = 1e9;
int n, k, m, q;
int c[N], sc[N];
int x[N], sx[N];
ll tr1[N], tr2[N];
void add(ll *tr, int a, int w) {
for(; a <= max(n, m + 1); a += a & -a) tr[a] += w;
}
ll ask(ll *tr, int a) {
ll w = 0;
for(; a; a -= a & -a) w += tr[a];
return w;
}
ll Out(int a, int b) {
if(a > b) swap(a, b);
return min(ask(tr1, b - 1) - ask(tr1, a - 1), ask(tr1, n) - ask(tr1, b - 1) + ask(tr1, a - 1));
}
bool type1(int a) {
return a <= n && a >= 1;
}
bool type2(int a) {
return a > n;
}
ll dis(int a, int b) {
if(a > b) swap(a, b);
if(a == b) return 0;
if(a == 1) {
if(type1(b)) {
ll res = Out(a, b);
res = min(res, ask(tr2, m + 1) + Out(k, b));
return res;
}
else {
ll res = ask(tr2, b - n);
res = min(res, ask(tr2, m + 1) - ask(tr2, b - n) + Out(1, k));
return res;
}
}
if(a == k || b == k) {
if(b == k) swap(a, b);
if(type1(a)) {
ll res = Out(a, b);
res = min(res, ask(tr2, m + 1) + Out(1, b));
return res;
}
else {
ll res = ask(tr2, m + 1) - ask(tr2, b - n);
res = min(res, ask(tr2, b - n) + Out(1, k));
return res;
}
}
if(type1(a) && type1(b)) {
ll res = Out(a, b);
res = min(res, dis(a, k) + dis(k, b));
res = min(res, dis(a, 1) + dis(1, b));
return res;
}
if(type2(a) && type2(b)) {
ll res = ask(tr2, b - n) - ask(tr2, a - n);
res = min(res, dis(a, k) + dis(k, b));
res = min(res, dis(a, 1) + dis(1, b));
return res;
}
ll res = INF * 100ll;
res = min(res, dis(a, k) + dis(k, b));
res = min(res, dis(a, 1) + dis(1, b));
return res;
}
int main() {
ios::sync_with_stdio(0); cin.tie(nullptr);
cin >> n >> k >> m >> q;
for(int i = 1; i <= n; i++) cin >> c[i];
for(int i = 1; i <= n; i++) {
sc[i] = 1, add(tr1, i, c[i]);
}
for(int i = 1; i <= m + 1; i++) {
cin >> x[i];
sx[i] = 1, add(tr2, i, x[i]);
}
for(; q; --q) {
char op[5]; int a, b; cin >> op;
if(op[0] == 'c') {
cin >> a;
if(sc[a] == 0) {
add(tr1, a, -INF);
add(tr1, a, c[a]);
sc[a] = 1;
}
else {
add(tr1, a, -c[a]);
add(tr1, a, INF);
sc[a] = 0;
}
}
else if(op[0] == 'x') {
cin >> a, ++a;
if(sx[a] == 0) {
add(tr2, a, -INF);
add(tr2, a, x[a]);
sx[a] = 1;
}
else {
add(tr2, a, -x[a]);
add(tr2, a, INF);
sx[a] = 0;
}
}
else {
cin >> a >> b;
ll value = dis(a, b);
if(value >= INF) cout << "impossible\n";
else cout << value << "\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13652kb
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: 13592kb
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
Wrong Answer
time: 407ms
memory: 34584kb
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...
output:
177406400 -4305418633691 -8590803552097 -7728772441497 impossible impossible impossible -35789803867 -7721784090897 -6863762505097 -8577786149097 -12011744287297 -29539447970 -22204496273 -23244223273 -37427863661 -11150801879697 -6853813717297 -12739614764 -6857316258491 -8602969176861 -36404757473...
result:
wrong answer 2nd lines differ - expected: '122264600', found: '-4305418633691'