QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397297#3746. 千万别用树套树SamponYWAC ✓174ms4780kbC++141.6kb2024-04-23 21:38:412024-04-23 21:38:42

Judging History

This is the latest submission verdict.

  • [2024-04-23 21:38:42]
  • Judged
  • Verdict: AC
  • Time: 174ms
  • Memory: 4780kb
  • [2024-04-23 21:38:41]
  • Submitted

answer

#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 100005
#define P 1000000007
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
  int s = 1;
  while(n) {
    if(n & 1) s = 1ll * s * p % P;
    p = 1ll * p * p % P, n >>= 1;
  }
  return s;
}
int n, m;
struct bit {
  int s[N];
  il void clr() {mems(s, 0);}
  il void add(int x, int v) {while(x <= n) s[x] += v, x += x & -x;}
  il int query(int x) {int v = 0; while(x) v += s[x], x ^= x & -x; return v;}
  il int query(int l, int r) {return query(r) - query(l - 1);}
} L, R;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  while(cin >> n >> m) {
    L.clr(), R.clr(); int A = 0;
    while(m--) {
      int op, a, b; cin >> op >> a >> b;
      if(op == 1) ++A, L.add(a, 1), R.add(b, 1);
      if(op == 2) cout << A - L.query(a + 1, n) - R.query(1, b - 1) << "\n";
    }
  }
  cerr << 1.0 * clock() / CLOCKS_PER_SEC;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 174ms
memory: 4780kb

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