QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#71816 | #2998. 皮配 | He_Ren | 0 | 3ms | 7848kb | C++23 | 3.5kb | 2023-01-12 01:22:32 | 2023-01-12 01:23:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
const int MAXQ = 1e5 + 5;
const int MAXD = 5e5 + 5;
struct BIT {
int tree[MAXD], n;
#define lowbit(x) ((x)&-(x))
inline void update(int x, int k) {
while (x <= n)
tree[x] += k,
x += lowbit(x);
}
inline void update(int l, int r, int k) {
update(l, k);
update(r + 1, -k);
}
inline int query(int x) {
int res = 0;
while (x)
res += tree[x],
x ^= lowbit(x);
return res;
}
} tree;
int begy[MAXN], enny[MAXN];
int fa[MAXN];
int find(int u) {
return fa[u] == u ? u : fa[u] = find(fa[u]);
}
int main(void) {
int n, A, B, C, begx, ennx;
scanf("%d%d%d%d%d%d", &n, &A, &B, &C, &begx, &ennx);
for (int i = 1; i <= n; ++i)
scanf("%d", &begy[i]);
for (int i = 1; i <= n; ++i)
scanf("%d", &enny[i]);
const ll BASE = 1e10;
set<pii> t;
vector< pair<ll, ll>> pt;
for (int i = n; i >= 1; --i) {
auto it = t.begin();
for (; it != t.end() && it -> first < enny[i]; ++it) {
int j = it -> second;
ldb
k1 = (ldb)(enny[i] - begy[i]) / (ennx - begx),
k2 = (ldb)(enny[j] - begy[j]) / (ennx - begx),
dx = (begy[j] - begy[i]) / (k1 - k2),
x = begx + dx,
y = begy[i] + dx * k1;
pt.emplace_back(round((x + y) * BASE), round((x - y) * BASE));
}
t.emplace_hint(it, enny[i], i);
}
static ll dsc[MAXD];
int dcnt = 0;
for (auto it : pt)
dsc[++dcnt] = it.second;
sort(dsc + 1, dsc + dcnt + 1);
dcnt = unique(dsc + 1, dsc + dcnt + 1) - dsc - 1;
int Q;
scanf("%d", &Q);
vector< tuple<ll, int, int, int>> eff;
while (Q--) {
int x, y, r;
scanf("%d%d%d", &x, &y, &r);
tie(x, y) = make_tuple(x + y, x - y);
int yl = lower_bound(dsc + 1, dsc + dcnt + 1, (y - r) * BASE) - dsc;
int yr = upper_bound(dsc + 1, dsc + dcnt + 1, (y + r) * BASE) - dsc - 1;
if (yl > yr)
continue;
eff.emplace_back((x - r) * BASE, 1, yl, yr);
eff.emplace_back((x + r) * BASE + 1, 2, yl, yr);
}
int useC = 0;
tree.n = dcnt;
sort(pt.begin(), pt.end());
sort(eff.begin(), eff.end());
for (int i = 0, j = 0; i < (int)pt.size(); ++i) {
for (; j < (int)eff.size() && get<0>(eff[j]) <= pt[i].first; ++j)
tree.update(get<2>(eff[j]), get<3>(eff[j]), get<1>(eff[j]) == 1 ? 1 : -1);
int cury = lower_bound(dsc + 1, dsc + dcnt + 1, pt[i].second) - dsc;
if (tree.query(cury))
++useC;
}
static int ord[MAXN];
iota(ord + 1, ord + n + 1, 1);
sort(ord + 1, ord + n + 1, [&](int x, int y) {
return enny[x] < enny[y];
});
iota(fa + 1, fa + n + 1, 1);
int ccnt = n;
for (int i = 1; i <= n; ++i)
if (find(i) != find(ord[i])) {
--ccnt;
fa[find(i)] = find(ord[i]);
}
int cr = (int)pt.size();
int must = n - ccnt;
ll ans1 = (ll)cr * A, ans2 = (ll)must * A + (ll)(cr - must) * B;
ans1 += (ll)useC * C;
ans2 += (ll)useC * C;
if (ans1 > ans2)
swap(ans1, ans2);
printf("%lld %lld", ans1, ans2);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5804kb
input:
5 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 3
output:
0 0
result:
wrong answer 1st lines differ - expected: '3', found: '0 0'
Test #2:
score: 0
Wrong Answer
time: 3ms
memory: 7696kb
input:
5 10 10 100 100 100 100 2 9 7 10 3 10 3 10 6 10 4 10 2 10 6 10 1 10 10 10 10 7 0 8 3 5 1 4 2 6 1 3 0 1 2 10 0 2 1 9 2 10 10 100 100 100 99 6 10 7 10 5 10 5 10 10 10 5 10 2 9 3 6 7 10 3 10 5 10 2 6 3 4 2 7 0 3 1 10 10 96 100 100 8 3 10 9 10 2 10 3 10 3 10 2 10 3 8 9 5 2 10 3 10 5 9 3 10 1 8 0 1 1 6 2...
output:
30 30
result:
wrong answer 1st lines differ - expected: '5184', found: '30 30'
Test #3:
score: 0
Wrong Answer
time: 3ms
memory: 7740kb
input:
5 20 20 93 93 100 97 6 3 19 7 6 10 2 7 5 6 11 7 4 10 17 10 1 7 19 4 14 5 20 7 15 3 6 7 5 6 15 10 3 7 5 10 15 6 1 7 0 20 20 100 100 100 100 20 10 7 9 2 8 5 10 4 6 1 10 4 10 17 10 1 6 5 10 12 10 9 6 12 8 1 10 10 10 13 10 12 10 10 10 13 7 18 10 0 20 20 98 96 100 10 3 5 8 5 19 7 3 6 19 5 3 6 5 4 6 5 6 3...
output:
120 120
result:
wrong answer 1st lines differ - expected: '826806650', found: '120 120'
Test #4:
score: 0
Wrong Answer
time: 3ms
memory: 7824kb
input:
5 30 30 100 98 94 97 12 2 27 5 25 5 24 4 14 5 4 6 22 7 2 3 30 8 1 2 7 5 2 2 20 5 11 7 15 5 18 3 11 3 1 4 25 5 11 2 15 4 12 5 3 8 12 7 6 3 30 8 19 5 13 3 21 9 4 3 0 30 30 93 99 92 93 24 3 23 10 17 5 22 5 17 7 29 10 18 6 7 5 17 6 9 7 3 6 16 6 9 5 10 4 6 5 20 6 2 7 20 5 3 3 9 3 2 5 29 6 9 8 1 4 12 5 1 ...
output:
210 210
result:
wrong answer 1st lines differ - expected: '217399345', found: '210 210'
Test #5:
score: 0
Wrong Answer
time: 3ms
memory: 5700kb
input:
5 30 30 482 500 500 500 17 10 15 10 25 10 14 8 9 10 1 10 15 10 23 10 13 8 15 9 15 8 20 10 19 10 6 10 18 8 23 10 3 10 28 10 13 10 2 10 15 10 17 10 1 10 2 10 14 10 11 10 29 7 24 10 14 10 30 10 13 15 3 25 3 18 2 23 2 1 3 7 0 4 2 20 0 26 2 9 1 3 2 30 2 24 1 30 30 485 500 500 489 22 10 7 10 10 10 1 8 9 1...
output:
240 240
result:
wrong answer 1st lines differ - expected: '335527780', found: '240 240'
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 7824kb
input:
5 500 500 998 974 1000 975 427 4 84 3 313 2 161 4 371 2 481 4 5 3 80 2 156 6 448 4 424 2 302 1 277 1 14 2 343 6 431 2 452 3 369 3 427 2 245 6 413 3 317 3 1 3 447 1 337 4 181 2 224 5 243 3 494 2 248 3 152 5 430 4 119 4 290 2 19 3 93 2 274 4 14 2 67 2 56 2 75 5 454 3 407 1 324 3 138 5 283 4 274 4 472 ...
output:
2000 2000
result:
wrong answer 1st lines differ - expected: '444961978', found: '2000 2000'
Test #7:
score: 0
Wrong Answer
time: 3ms
memory: 7788kb
input:
5 500 30 1000 982 976 986 1 2 23 3 22 1 5 6 22 4 27 2 22 5 18 6 19 1 11 4 30 2 20 4 2 3 18 2 2 3 18 4 8 2 27 4 3 3 27 4 19 5 2 1 28 4 18 2 10 1 11 4 29 3 20 2 22 3 4 2 4 4 26 3 3 3 3 4 3 5 18 3 3 1 4 3 11 3 15 6 19 2 21 3 23 4 12 2 14 4 2 1 30 2 15 4 10 3 21 3 12 6 11 3 14 2 5 2 30 1 11 2 25 4 13 2 ...
output:
1500 1500
result:
wrong answer 1st lines differ - expected: '721598186', found: '1500 1500'
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 5680kb
input:
5 500 500 975 1000 1000 1000 322 4 4 1 327 6 287 3 352 3 493 3 8 4 89 1 348 3 277 2 158 2 375 2 457 3 155 2 94 2 423 2 407 4 405 2 474 4 44 2 103 3 430 4 61 2 83 2 314 2 143 5 468 2 481 3 241 2 388 4 453 3 301 3 225 4 375 2 181 5 259 5 220 4 126 3 301 4 150 1 383 1 394 3 177 1 329 4 448 1 394 3 129 ...
output:
2500 2500
result:
wrong answer 1st lines differ - expected: '139292860', found: '2500 2500'
Test #9:
score: 0
Wrong Answer
time: 3ms
memory: 7792kb
input:
5 1000 1000 2500 2500 2500 2500 285 3 51 3 740 5 140 4 758 4 740 2 493 7 155 3 30 6 380 2 235 3 447 5 500 4 402 2 358 2 936 4 48 4 793 4 994 1 668 5 607 3 694 4 426 4 377 7 314 7 83 7 948 3 423 6 229 4 920 3 498 5 262 3 22 4 25 3 661 4 420 2 689 5 509 5 401 3 213 4 286 4 699 3 466 4 430 3 734 4 420 ...
output:
5000 5000
result:
wrong answer 1st lines differ - expected: '803471990', found: '5000 5000'
Test #10:
score: 0
Wrong Answer
time: 0ms
memory: 7848kb
input:
5 1000 1000 2500 2500 2500 2500 801 5 102 2 581 5 589 5 493 6 214 2 604 10 391 3 7 2 555 4 594 3 614 8 230 5 900 4 605 5 869 6 991 4 820 2 124 4 630 2 694 3 244 6 170 4 8 2 360 1 394 3 512 7 823 3 89 3 988 5 433 4 858 6 362 4 995 4 181 3 718 3 275 2 325 4 11 4 5 2 222 4 209 5 562 1 158 2 908 3 496 3...
output:
5000 5000
result:
wrong answer 1st lines differ - expected: '517838564', found: '5000 5000'