QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#534050#62. Examinationisirazeev0 1ms6232kbC++202.3kb2024-08-26 20:00:062024-08-26 20:00:07

Judging History

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

  • [2024-08-26 20:00:07]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:6232kb
  • [2024-08-26 20:00:06]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = (int) 1e5 * 2 + 10;

struct Node {
    int a, b, c, ind, cost;
};

struct BIT {
    vector<int> f;
    int N;

    void init(int n) {
        N = n + 2;
        f.resize(n + 2, 0);
    }

    void update(int i, int val) {
        for (; i < N; i += (i & (-i)))
            f[i] += val;
    }

    int sum(int r) {
        int res = 0;
        for (; r > 0; r -= (r & (-r)))
            res += f[r];
        return res;
    }
};

vector<Node> v;
int ans[N];

BIT bit;

void DivideAndConquer(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2, a = l, b = mid + 1, sum = 0;
    DivideAndConquer(l, mid), DivideAndConquer(mid + 1, r);
    vector<pair<int, int>> record;
    vector<Node> tmp;
    while (a <= mid && b <= r) {
        if (v[a].b >= v[b].b) {
            bit.update(v[a].c, v[a].cost), record.emplace_back(v[a].c, v[a].cost);
            sum += v[a].cost, tmp.emplace_back(v[a++]);
        } else {
            ans[v[b].ind] += sum - bit.sum(v[b].c - 1), tmp.emplace_back(v[b++]);
        }
    }
    while (a <= mid) tmp.emplace_back(v[a++]);
    while (b <= r) ans[v[b].ind] += sum - bit.sum(v[b].c - 1), tmp.emplace_back(v[b++]);
    for (auto [ind, val]: record) bit.update(ind, -val);
    for (int i = l; i <= r; i++) v[i] = tmp[i - l];
}

set<int> all;
map<int, int> to;

void compress(vector<int> &a) {
    all.clear(), to.clear();
    int cnt = 1;
    for (int i: a) all.insert(i);
    for (int i: all) to[i] = cnt++;
    for (int &i: a) i = to[i];
}

void solve() {
    bit.init(2 * N);
    vector<int> A, B, C;
    sort(v.begin(), v.end(), [&](Node a, Node b) {
        return (a.a != b.a ? a.a > b.a : (a.b != b.b ? a.b > b.b : a.c > b.c));
    });
    DivideAndConquer(0, (int) v.size() - 1);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int s, t;
        cin >> s >> t;
        v.emplace_back(s, t, s + t, q, 1);
    }
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        v.emplace_back(x, y, z, i, 0);
    }
    solve();
    for (int i = 0; i < q; i++)
        cout << ans[i] << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 2
Accepted
time: 1ms
memory: 6160kb

input:

10 10
28 2
78 81
39 79
61 31
36 99
90 5
20 55
91 4
48 19
80 7
52 43 78
64 65 171
34 68 124
37 80 161
53 19 123
49 58 109
95 46 30
45 48 60
47 13 54
64 30 144

output:

1
0
2
0
1
1
0
1
3
1

result:

ok 10 lines

Test #2:

score: 2
Accepted
time: 0ms
memory: 6196kb

input:

10 10
6 67
36 99
13 45
100 87
60 72
55 41
62 92
55 39
90 22
0 99
34 89 79
17 17 23
60 26 171
29 88 190
32 71 98
20 29 192
50 7 34
14 21 139
54 35 103
86 91 1

output:

2
7
1
0
4
0
6
2
3
0

result:

ok 10 lines

Test #3:

score: 2
Accepted
time: 0ms
memory: 6232kb

input:

10 10
67 72
94 99
34 22
1 71
68 18
90 94
29 44
98 61
46 9
94 76
73 36 11
30 26 75
5 85 112
38 35 111
39 72 143
6 64 130
31 24 134
82 86 188
80 20 151
91 32 62

output:

4
5
2
5
3
4
5
1
4
3

result:

ok 10 lines

Test #4:

score: 0
Runtime Error

input:

10 10
667489048 282547819
694873877 525794923
605957229 147658688
928289876 455560133
465507205 531350815
397977066 913356070
351069660 834164613
611261253 238522918
683770744 737447844
351350094 473152918
514777487 599392520 569824365
137189600 455145855 1628925058
608994260 433029864 1934471803
80...

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #19:

score: 0
Time Limit Exceeded

input:

100000 100000
26753 11234
32815 62591
34318 93262
77179 57605
88208 33327
48449 99060
42403 58561
85715 7001
2418 90938
77409 6957
546 83283
53957 8374
49470 1483
65866 64950
4269 8745
19041 85833
22344 90706
92926 35603
54697 75311
72601 66401
77598 8193
3751 54202
32710 5877
23835 38264
34381 3338...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%