QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#102773 | #5669. Traveling in Jade City | Joler# | WA | 451ms | 81072kb | C++20 | 6.8kb | 2023-05-03 17:37:18 | 2023-05-03 17:37:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#ifdef LOCAL
template<class t,class u>ostream& operator<<(ostream& os,const pair<t,u>& p){return os<<"("<<p.first<<","<<p.second<<")";}
#endif
template<class t>ostream& operator<<(ostream& os,const vector<t>& v){if(v.size())os<<v[0];for(int i=1; i<v.size(); i++)os<<' '<<v[i]; return os;}
const int inf = 0x3f3f3f3f;
const ll INF = inf;
int n, m, t, k, a, b, c, d, cnt, mark, an, oT_To, x, y, z, q;
ll ans;
int check(int x) {
int res = 0;
if (x == 1 || x == k) res |= 7;
if (x < k) res |= 1;
if (x > k && x <= n) res |= 2;
if (x > n) res |= 3;
}
template<typename T>
struct Fenwick {
int n;
std::vector<T> a;
Fenwick(int n = 0) {
init(n);
}
void init(int n) {
this->n = n;
a.assign(n, T());
}
void add(int x, T v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i - 1] += v;
}
}
T sum(int x) {
auto ans = T();
for (int i = x; i > 0; i -= i & -i) {
ans += a[i - 1];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
};
struct Solver {
void solve() {
cin >> n >> k >> m >> q;
vector <ll> vc (n+1), vx(m+1);
vector vf(3, Fenwick<ll>(n+m+2) );
auto VC(vc), VX(vx);
for (int i = 1; i < k; ++i) {
cin >> VC[i];
vf[0].add(i+1, VC[i]);
}
for (int i = k; i <= n; ++i) {
cin >> VC[i];
vf[1].add(i+1, VC[i]);
}
for (int i = 0; i <= m; ++i) {
cin >> VX[i];
vf[2].add(i+2, VX[i]);
}
auto get1 = [&](int x){
ll res = INF;
if (x > n) {
x -= n;
return vf[2].rangeSum(1, x+1);
} else {
if (x >= k) {
res = min(res, vf[1].rangeSum(x+1, n+2));
}
if (x <= k) {
res = min(res, vf[0].rangeSum(1, x+1));
}
}
return res;
};
auto getk = [&](int x) {
ll res = INF;
if (x > n) {
x -= n;
return vf[2].rangeSum(x+1, m+2);
} else {
if (x >= k) {
res = min(res, vf[1].rangeSum(k+1, x+1));
} else {
res = min(res, vf[0].rangeSum(x+1, k+1));
}
}
return res;
};
// cout << "vf[0].rangeSum(2, 4): " << vf[0].rangeSum(4, 5) << '\n';
char ch;
while (q--) {
cin >> ch;
if (ch == 'x') {
cin >> a;
if (vx[a]) {
vf[2].add(a+2, -INF);
} else {
vf[2].add(a+2, INF);
}
vx[a] = !vx[a];
} else if (ch == 'c') {
cin >> a;
if (vc[a]) {
if (a < k) {
vf[0].add(a+1, -INF);
} else {
vf[1].add(a+1, -INF);
}
} else {
if (a < k) {
vf[0].add(a+1, INF);
} else {
vf[1].add(a+1, INF);
}
}
vc[a] = !vc[a];
} else if (ch == 'q') {
cin >> a >> b;
if (a > b) swap(a, b);
ll a1 = get1(a), ak = getk(a);
ll b1 = get1(b), bk = getk(b);
ll k1 = vf[2].sum(m+3);
ans = min({INF, a1+b1, ak+bk, a1+k1+bk, ak+k1+b1});
if (a > n && b > n) {
ans = min(ans, abs(a1-b1));
} else {
if (a >= k && b >= k) {
ans = min(ans, vf[1].rangeSum(a+1, b+1));
}
if (a <= k && b <= k) {
ans = min(ans, vf[0].rangeSum(a+1, b+1));
}
}
if (ans >= INF) {
cout << "impossible\n";
} else cout << ans << '\n';
}
}
//
// v1[0][1] = v1[1][1] = v1[2][1] = 0;
// vk[0][k] = vk[1][k] = vk[2][k] = 0;
// // 0 -> 1-k
// for (int i = 2; i <= k; ++i) {
// v1[0][i] = v1[0][i-1] + vc[i-1];
// }
// for (int i = k-1; i >= 1; --i) {
// vk[0][i] = vk[0][i+1] + vc[i];
// }
//
// // 1 -> k-n
// for (int i = k+1; i <= n; ++i) {
// vk[1][i] = vk[1][i-1] + vc[i-1];
// }
// v1[1][n+1] = 0;
// for (int i = n; i >= k; --i) {
// v1[1][i] = v1[1][i+1] + vc[i];
// }
// vk[1][1] = v1[1][k];
// v1[1][n+1] = INF;
//
//
//
// // 2 -> 1-n+1-n+m-k
// v1[2][n+1] = vx[0];
// for (int i = n+2; i <= n+m; ++i) {
// v1[2][i] = v1[2][i-1] + vx[i-n-1];
// }
// vk[2][1] = v1[2][k] = v1[2][n+m] + vx[m];
// vk[2][n+m+1] = 0;
// for (int i = n+m; i >= n+1; --i) {
// vk[2][i] = vk[2][i+1] + vx[i - n];
// }
// vk[2][n+m+1] = INF;
//
//
//
// while (vp.size()) {
// auto [x, y] = vp.back(); vp.pop_back();
// if (y > 0) {
// ans = INF;
// int fx = check(x), fy = check(y);
// ll xto1 = min({v1[0][x], v1[1][x], v1[2][x]});
// ll xtok = min({vk[0][x], vk[1][x], vk[2][x]});
// ll yto1 = min({v1[0][y], v1[1][y], v1[2][y]});
// ll ytok = min({vk[0][y], vk[1][y], vk[2][y]});
// ans = min({ans, xto1 + yto1, xtok + ytok, xto1 + v1[2][k] + ytok, xtok + v1[2][k] + yto1});
// for (int i : {0, 1, 2}) {
// int j = i<<1;
// if ((fx&j) && (fy&j)) {
// ans = min(ans, abs(v1[i][x] - v1[])
// }
// }
//
// }
// else {
// y = -y;
// if (x == 0) {
// vx[y] = VX[y];
// // do it
// assert(0);
// } else {
// vc[y] = VX[y];
// // do it
// assert(0);
//
// }
// }
// }
}
};
int main () {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// cout << "INF: " << INF << '\n';
oT_To = 1;
// cin >> oT_To;
while (oT_To--) {
Solver solver;
solver.solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3388kb
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: 3392kb
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: 451ms
memory: 81072kb
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:
377406200 122264600 181690400 impossible impossible impossible impossible impossible impossible impossible impossible impossible 29295000 impossible 22163000 impossible impossible impossible 11422200 impossible 62579800 impossible 164661200 impossible 20157200 impossible impossible impossible imposs...
result:
wrong answer 1st lines differ - expected: '177406400', found: '377406200'