QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387693 | #3746. 千万别用树套树 | NYOJ-1 | AC ✓ | 163ms | 4668kb | C++17 | 651b | 2024-04-12 18:54:07 | 2024-04-12 18:54:11 |
Judging History
answer
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 1000010
#define low(x) (x&-x)
typedef long long ll;
int n, q, t[maxn][2];
void add(int x, int flg) {
while (x <= n) {
t[x][flg] += 1;
x += low(x);
}
}
int sum(int x, int flg) {
int res = 0;
while (x > 0) {
res += t[x][flg];
x -= low(x);
}
return res;
}
int main() {
while (~scanf("%d%d", &n, &q)) {
for (int i = 1; i <= n; i++) t[i][0] = t[i][1] = 0;
for (int i = 1; i <= q; i++) {
int op, l, r; scanf("%d%d%d", &op, &l, &r);
if (op == 1) {
add(l, 0); add(r, 1);
}
else {
printf("%d\n", sum(l, 0) - sum(r - 1, 1));
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 163ms
memory: 4668kb
input:
100000 100000 1 48500 63742 1 43673 89780 1 6471 44388 1 68054 71541 1 30056 91431 1 49687 70537 2 46899 46900 1 5165 57954 1 85892 88481 2 18060 18062 2 45289 45289 1 18927 67848 1 17389 96139 1 63451 92197 1 15473 87341 1 15162 15744 1 76728 99645 2 48730 48731 2 20886 20888 1 9756 67424 1 23175 4...
output:
2 2 3 7 5 8 9 4 6 2 11 13 13 10 13 15 9 10 14 16 17 16 16 15 2 4 11 6 11 12 23 9 26 3 28 20 12 12 22 30 5 27 6 29 10 14 27 6 17 15 9 30 20 34 7 36 15 8 32 16 21 40 19 2 1 12 12 39 37 13 19 20 1 9 37 1 41 40 20 34 45 43 27 30 47 29 13 50 41 44 29 35 38 53 2 46 54 36 56 58 45 32 42 26 52 42 60 1 4 25 ...
result:
ok 500497 numbers