QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#71816#2998. 皮配He_Ren0 3ms7848kbC++233.5kb2023-01-12 01:22:322023-01-12 01:23:44

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-12 01:23:44]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:7848kb
  • [2023-01-12 01:22:32]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'