QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534050 | #62. Examination | isirazeev | 0 | 1ms | 6232kb | C++20 | 2.3kb | 2024-08-26 20:00:06 | 2024-08-26 20:00:07 |
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%