QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #184351 | #5669. Traveling in Jade City | ucup-team1508# | WA | 906ms | 124376kb | C++14 | 6.2kb | 2023-09-20 17:35:54 | 2023-09-20 17:35:54 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 2e6 + 10;
const int inf = 1e18;
typedef array<int, 3> a3;
a3 operator + (const a3 &x, const a3 &y) {
return {x[0] + y[0], x[1] + y[1], x[2] + y[2]};
}
int n, k, m, q, f1[N << 2], c[N << 1], f2[N << 2], f3[N << 2];
void pull(int k) {f2[k] = f2[k << 1] + f2[k << 1 | 1];}
void build(int k, int l, int r) {
if(l == r) {
f1[k] = c[l], f2[k] = f3[k] = 1;
return;
}
int mid = l + r >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
pull(k);
f1[k] = f1[k << 1] + f1[k << 1 | 1];
f3[k] = f3[k << 1] + f3[k << 1 | 1];
}
void update(int k, int l, int r, int x) {
if(l == r) {
f2[k] ^= 1;
return;
}
int mid = l + r >> 1;
if(mid >= x) update(k << 1, l, mid, x);
else update(k << 1 | 1, mid + 1, r, x);
pull(k);
}
a3 cal(int k, int l, int r, int x, int y) {
if(x > y) return {0, 0, 0};
if(l == x && r == y) {
return {f1[k], f2[k], f3[k]};
}
int mid = l + r >> 1;
if(mid >= y) return cal(k << 1, l, mid, x, y);
else if(mid < x) return cal(k << 1 | 1, mid + 1, r, x, y);
else return cal(k << 1, l, mid, x, mid) + cal(k << 1 | 1, mid + 1, r, mid + 1, y);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> m >> q;
F(i, 1, n + m + 1) cin >> c[i];
build(1, 1, n + m + 1);
// F(i, 1, n + m + 1) {
// auto [x, y, z] = cal(1, 1, n + m + 1, i, i);
// cout << x << " \n" [i == n + m + 1];
// }
F(i, 1, q) {
char op; cin >> op;
if(op == 'x') {
int x; cin >> x;
update(1, 1, n + m + 1, x + n + 1);
} else if(op == 'c') {
int x; cin >> x;
update(1, 1, n + m + 1, x);
} else {
int u, v; cin >> u >> v;
if(u > v) swap(u, v);
int res = inf;
if(v <= n) {
if(v <= k) {
{
auto [x, y, z] = cal(1, 1, n + m + 1, u, v - 1);
if(y == z) res = min(res, x);
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, 1, u - 1) + cal(1, 1, n + m + 1, v, n);
if(y == z) res = min(res, x);
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, 1, u - 1) + cal(1, 1, n + m + 1, v, k - 1) + cal(1, 1, n + m + 1, n + 1, n + m + 1);
if(y == z) res = min(res, x);
}
} else if(u > k) {
{
auto [x, y, z] = cal(1, 1, n + m + 1, u, v - 1);
if(y == z) res = min(res, x);
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, 1, u - 1) + cal(1, 1, n + m + 1, v, n);
if(y == z) res = min(res, x);
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, k, u - 1) + cal(1, 1, n + m + 1, v, n) + cal(1, 1, n + m + 1, n + 1, n + m + 1);
if(y == z) res = min(res, x);
}
} else {
{
auto [x, y, z] = cal(1, 1, n + m + 1, u, v - 1);
if(y == z) res = min(res, x);
// cout << x << " ";
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, 1, u - 1) + cal(1, 1, n + m + 1, v, n);
if(y == z) res = min(res, x);
// cout << x << " ";
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, 1, u - 1) + cal(1, 1, n + m + 1, k, v - 1) + cal(1, 1, n + m + 1, n + 1, n + m + 1);
if(y == z) res = min(res, x);
// cout << x << " ";
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, u, k - 1) + cal(1, 1, n + m + 1, v, n) + cal(1, 1, n + m + 1, n + 1, n + m + 1);
if(y == z) res = min(res, x);
// cout << x << "\n";
}
}
} else if(u > n) {
{
auto [x, y, z] = cal(1, 1, n + m + 1, u + 1, v);
if(y == z) res = min(res, x);
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, n + 1, u) + cal(1, 1, n + m + 1, v + 1, n + m + 1) + cal(1, 1, n + m + 1, 1, k - 1);
if(y == z) res = min(res, x);
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, n + 1, u) + cal(1, 1, n + m + 1, v + 1, n + m + 1) + cal(1, 1, n + m + 1, k, n);
if(y == z) res = min(res, x);
}
} else {
if(u <= k) {
{
auto [x, y, z] = cal(1, 1, n + m + 1, 1, u - 1) + cal(1, 1, n + m + 1, n + 1, v);
if(y == z) res = min(res, x);
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, u, k - 1) + cal(1, 1, n + m + 1, v + 1, n + m + 1);
if(y == z) res = min(res, x);
}
} else {
{
auto [x, y, z] = cal(1, 1, n + m + 1, v + 1, n + m + 1) + cal(1, 1, n + m + 1, k, u - 1);
if(y == z) res = min(res, x);
}
{
auto [x, y, z] = cal(1, 1, n + m + 1, u, n) + cal(1, 1, n + m + 1, n + 1, v);
if(y == z) res = min(res, x);
}
}
}
if(res == inf) cout << "impossible\n";
else cout << res << "\n";
}
}
return 0;
}
/*
4 3 1 4
2 3 8 4
1 1
q 3 3
q 1 5
q 5 4
q 3 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9756kb
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: 0ms
memory: 9844kb
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: 906ms
memory: 124376kb
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 122264600 181690600 impossible impossible impossible impossible impossible impossible impossible impossible impossible 29295200 impossible 22163200 impossible impossible impossible 11422200 impossible 62579800 impossible 35339400 impossible 20157200 impossible impossible impossible impossi...
result:
wrong answer 3rd lines differ - expected: '70328400', found: '181690600'