QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180548 | #5669. Traveling in Jade City | arseny_y | TL | 2915ms | 396872kb | C++20 | 4.9kb | 2023-09-15 23:10:19 | 2023-09-15 23:10:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(), (a).end()
#define X first
#define Y second
const int MOD = 1e9 + 7, MAXN = 2e6 + 1337;
const ld EPS = 1e-6;
void solve();
int main() {
#ifdef LOCAL
freopen("../main_cpp/input.txt", "r", stdin);
#else
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
}
#define int ll
const int INF = LLONG_MAX / 10000;
const int R = 1 << 21;
struct Tree {
vector<int> t;
Tree() {
t.resize(R * 2, 1);
}
void relax(int i) {
while (i) {
t[i] = min(t[i * 2], t[i * 2 + 1]), i /= 2;
}
}
void add(int i) {
t[i += R] = 1, i /= 2, relax(i);
}
void del(int i) {
t[i += R] = 0, i /= 2, relax(i);
}
int mn(int ql, int qr) {
int mn = 1;
for (ql += R, qr += R; ql <= qr; ql >>= 1, qr >>= 1) {
if (ql & 1) mn = min(mn, t[ql++]);
if (~qr & 1) mn = min(mn, t[qr--]);
}
return mn;
}
};
int n, k, m, q;
struct Round {
Tree tree;
vector<int> indv, indedge_dick, indedge_round;
vector<int> c_dick, c_round;
vector<int> pref;
int all_sm;
void init(const vector<tuple<int, int, int, int>> t) {
c_dick.resize(MAXN, 1), c_round.resize(MAXN, 1), indv.resize(MAXN, -1), indedge_dick.resize(MAXN,
-1), indedge_round.resize(
MAXN, -1);
pref.resize(MAXN, 0);
all_sm = 0;
for (int i = 0; i < t.size(); ++i) {
tree.add(i);
auto [w, vertex, index_edge, f] = t[i];
indv[vertex] = i;
all_sm += w;
if (f) {
indedge_dick[index_edge] = i;
} else {
indedge_round[index_edge] = i;
}
pref[i] = w + (i > 0 ? pref[i - 1] : 0);
}
}
void change_dick(int i) {
c_dick[i] = -c_dick[i];
if (indedge_dick[i] == -1) return;
if (c_dick[i] == -1) {
tree.del(indedge_dick[i]);
} else {
tree.add(indedge_dick[i]);
}
}
void change_round(int i) {
c_round[i] = -c_round[i];
if (indedge_round[i] == -1) return;
if (c_round[i] == -1) {
tree.del(indedge_round[i]);
} else {
tree.add(indedge_round[i]);
}
}
int gett(int l, int r) {
return pref[r - 1] - (l == 0 ? 0 : pref[l - 1]);
}
int get(int l, int r) {
if (tree.mn(l, r - 1) == 0) return INF;
return gett(l, r);
}
int find(int u, int v) {
if (u == v) return 0;
int i1 = indv[u], i2 = indv[v];
if (min(i1, i2) == -1) return INF;
if (i1 > i2) swap(i1, i2);
int ans = get(i1, i2);
if (min(tree.mn(i2, R - 1), tree.mn(0, i1 - 1)) > 0) {
ans = min(ans, all_sm - gett(i1, i2));
}
return ans;
}
};
void solve() {
cin >> n >> k >> m >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
++m;
vector<int> b(m);
for (auto &i: b) {
cin >> i;
}
Round roundleft, roundright;
{
vector<tuple<int, int, int, int>> t; // {w, vertex, index_edge}
for (int i = 1; i < k; ++i) {
t.emplace_back(a[i], i, i, 0);
}
for (int i = m - 1, v = n + m; i >= 0; --i, --v) {
t.emplace_back(b[i], (v == n + m ? k : v), i, 1);
}
roundright.init(t);
}
{
vector<tuple<int, int, int, int>> t; // {w, vertex, index_edge}
for (int i = k; i <= n; ++i) {
t.emplace_back(a[i], i, i, 0);
}
for (int i = 0, v = n; i < m; ++i, ++v) {
t.emplace_back(b[i], (v == n ? 1 : v), i, 1);
}
roundleft.init(t);
}
auto get = [&](int u, int v) -> int {
return min(roundleft.find(u, v), roundright.find(u, v));
};
while (q--) {
char c;
cin >> c;
if (c == 'c') {
int i;
cin >> i;
roundleft.change_round(i), roundright.change_round(i);
} else if (c == 'x') {
int i;
cin >> i;
roundleft.change_dick(i), roundright.change_dick(i);
} else {
int u, v;
cin >> u >> v;
int dst1k = get(1, k);
int ans = get(u, v);
ans = min({ans, min(get(u, 1) + get(k, v), get(u, k) + get(1, v)) + dst1k});
ans = min({ans, get(u, 1) + get(1, v), get(u, k) + get(k, v)});
cout << (ans >= INF ? "impossible" : to_string(ans)) << "\n";
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 15ms
memory: 256420kb
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: 16ms
memory: 256292kb
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: 0
Accepted
time: 1987ms
memory: 335924kb
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 70328400 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 impossib...
result:
ok 500003 lines
Test #4:
score: 0
Accepted
time: 2168ms
memory: 298504kb
input:
100000 25123 500000 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 200 ...
output:
4243800 37968200 35427000 52078200 5074200 70821200 13901400 13614600 8774800 68958800 49822200 31077400 impossible 45392400 48946000 76885400 37532600 34416200 impossible 20744200 71652000 21288000 7501600 70315400 14721800 impossible 12981800 81039600 9506800 impossible 33487200 53520200 impossibl...
result:
ok 500004 lines
Test #5:
score: 0
Accepted
time: 2616ms
memory: 363236kb
input:
1000000 543210 999999 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 20...
output:
43962400 803800 153423600 impossible impossible impossible impossible impossible 191566200 impossible impossible impossible impossible 84524200 impossible 8790000 impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible 86439200 20798400 impossibl...
result:
ok 666666 lines
Test #6:
score: 0
Accepted
time: 2491ms
memory: 396872kb
input:
999999 2 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 200 200...
output:
103577000 40419800 44334400 117613400 27695600 101675800 93767600 impossible impossible 41683400 58145400 impossible impossible 38841000 impossible impossible 60723200 impossible impossible impossible 35102200 360200 impossible 64912000 48484000 impossible impossible impossible impossible impossible...
result:
ok 666666 lines
Test #7:
score: 0
Accepted
time: 2915ms
memory: 326564kb
input:
10 5 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 200 200 200...
output:
94819200 65730000 72994800 49117800 104138800 186947800 44801800 49390200 165897000 78473600 43124000 7660200 impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible imp...
result:
ok 666666 lines
Test #8:
score: 0
Accepted
time: 1856ms
memory: 304104kb
input:
1000000 371220 10 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 200 20...
output:
20563800 35454600 impossible impossible impossible 787600 impossible 34108400 impossible impossible impossible 18207600 impossible impossible impossible 55803600 impossible impossible 2024800 impossible impossible impossible impossible impossible impossible impossible impossible impossible impossibl...
result:
ok 833321 lines
Test #9:
score: -100
Time Limit Exceeded
input:
1000000 543210 1000000 1000000 55 172 71 52 118 20 70 172 64 49 84 89 145 22 84 186 131 52 18 28 59 73 88 52 82 11 75 157 71 55 184 129 87 109 153 139 121 184 37 96 123 102 186 99 191 116 28 45 198 166 103 164 171 149 66 193 65 110 191 123 51 138 100 146 139 129 168 127 125 55 178 27 80 87 101 21 13...
output:
30670961 48913371 7774973 27843322 64930666 19787521 32236183 33937440 21950724 29313510 69061178 48818521 12208541 65243879 41433227 67580303 14884583 56319432 47932125 69665033 29946609 71525011 9854513 34362272 26512727 21612559 10235684 36689531 31170755 61421169 9720654 34948295 29798373 623856...