oj.uz

Submission #1097864

# Submission time Handle Problem Language Result Execution time Memory
1097864 2024-10-08T13:16:57 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 1735 ms 689268 KB 
#include <bits/stdc++.h>
 
#define ll int
#define fr(i, d, c) for(ll i = d; i <= c; i++)
#define fl(i, d, c) for(ll i = d; i >= c; i--)
const int N = 1e5 + 9;
using namespace std;
    
ll n, q, kq[N];
vector<tuple<ll, ll, ll, ll, ll>> qr;
vector<ll> nen; 
 
struct node {
  ll nx[2], cnt;
};
 
struct trie {
  vector<node> t;
 
  trie() {
    t.emplace_back();
  }
 
  void up(ll x, ll val) {
    ll cur = 0;
    for(ll j = 30; j >= 0; j--) {
      ll y = 0;
      if(x >> j & 1) y = 1;
      if(!t[cur].nx[y]) {
        t[cur].nx[y] = t.size();
        t.emplace_back();
      } 
      cur = t[cur].nx[y];
      t[cur].cnt += val; 
    }
  }
 
  ll get(ll x) {
    ll cur = 0, ans = 0;
    for(ll j = 30; j >= 0; j--) {
      ll y = 0;
      if(x >> j & 1) y = 1;
 
      if(y == 0) {
        ll z = t[cur].nx[1];
        if(z) ans += t[z].cnt;
      }
 
      if(!t[cur].nx[y]) break;
 
      cur = t[cur].nx[y];
      if(j == 0) ans += t[cur].cnt; 
    }
    return ans;
  }
} tree[10 * N];
 
void up(ll pos, ll val, ll num, ll id = 1, ll l = 1, ll r = nen.size()) {
  if(l == r) {
    tree[id].up(val, num);
  }
  else {
    ll mid = (l + r) / 2;
    if(pos <= mid) up(pos, val, num, id * 2, l, mid);
    else up(pos, val, num, id * 2 + 1, mid + 1, r);
    tree[id].up(val, num);
  }
}
 
ll get(ll st, ll en, ll val, ll id = 1, ll l = 1, ll r = nen.size()) {
  if(st > r || en < l) return 0;
  if(st <= l && r <= en) return tree[id].get(val);
  ll mid = (l + r) / 2;
  return get(st, en, val, id * 2, l, mid) + get(st, en, val, id * 2 + 1, mid + 1, r);
}
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  cin >> n >> q;
  fr(i, 1, n) {
    ll x, y;
    cin>> x >> y;
    nen.push_back(y);
    qr.push_back({x, 1, y, 0, 0});
  }
  fr(i, 1, q) {
    ll x, y, z;
    cin>> x >> y >> z;
    nen.push_back(y);
    qr.push_back({x, 0, y, z, i});
  }
  
  sort(nen.begin(), nen.end());
  nen.erase(unique(nen.begin(), nen.end()), nen.end());
  sort(qr.begin(), qr.end());  
  reverse(qr.begin(), qr.end());
 
  for(auto [x, t, y, z, id]: qr) {
    if(t == 1) {
      ll pos = upper_bound(nen.begin(), nen.end(), y) - nen.begin();
      up(pos, x + y, 1);
    }
    else {
      ll pos = upper_bound(nen.begin(), nen.end(), y) - nen.begin();
      kq[id] = get(pos, nen.size(), z);
    }
  }
 
  fr(i, 1, q) cout<<kq[i]<<'\n'; 
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 55132 KB Output is correct
2 Correct 47 ms 55012 KB Output is correct
3 Correct 53 ms 55008 KB Output is correct
4 Correct 66 ms 55120 KB Output is correct
5 Correct 60 ms 55376 KB Output is correct
6 Correct 61 ms 55120 KB Output is correct
7 Correct 88 ms 71496 KB Output is correct
8 Correct 84 ms 71236 KB Output is correct
9 Correct 79 ms 71072 KB Output is correct
10 Correct 58 ms 59972 KB Output is correct
11 Correct 80 ms 68164 KB Output is correct
12 Correct 59 ms 55376 KB Output is correct
13 Correct 77 ms 70980 KB Output is correct
14 Correct 80 ms 71476 KB Output is correct
15 Correct 85 ms 71132 KB Output is correct
16 Correct 79 ms 68228 KB Output is correct
17 Correct 69 ms 57028 KB Output is correct
18 Correct 60 ms 55436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 353492 KB Output is correct
2 Correct 1116 ms 353328 KB Output is correct
3 Correct 1088 ms 352848 KB Output is correct
4 Correct 175 ms 86740 KB Output is correct
5 Correct 597 ms 186848 KB Output is correct
6 Correct 151 ms 62900 KB Output is correct
7 Correct 999 ms 352988 KB Output is correct
8 Correct 1000 ms 338200 KB Output is correct
9 Correct 1018 ms 338412 KB Output is correct
10 Correct 454 ms 171476 KB Output is correct
11 Correct 138 ms 70100 KB Output is correct
12 Correct 129 ms 62688 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 353492 KB Output is correct
2 Correct 1116 ms 353328 KB Output is correct
3 Correct 1088 ms 352848 KB Output is correct
4 Correct 175 ms 86740 KB Output is correct
5 Correct 597 ms 186848 KB Output is correct
6 Correct 151 ms 62900 KB Output is correct
7 Correct 999 ms 352988 KB Output is correct
8 Correct 1000 ms 338200 KB Output is correct
9 Correct 1018 ms 338412 KB Output is correct
10 Correct 454 ms 171476 KB Output is correct
11 Correct 138 ms 70100 KB Output is correct
12 Correct 129 ms 62688 KB Output is correct
13 Correct 1217 ms 353212 KB Output is correct
14 Correct 1018 ms 353172 KB Output is correct
15 Correct 973 ms 353332 KB Output is correct
16 Correct 192 ms 86136 KB Output is correct
17 Correct 699 ms 187876 KB Output is correct
18 Correct 170 ms 62920 KB Output is correct
19 Correct 1179 ms 354000 KB Output is correct
20 Correct 1212 ms 353744 KB Output is correct
21 Correct 1193 ms 345300 KB Output is correct
22 Correct 446 ms 171732 KB Output is correct
23 Correct 124 ms 70100 KB Output is correct
24 Correct 119 ms 62692 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 55132 KB Output is correct
2 Correct 47 ms 55012 KB Output is correct
3 Correct 53 ms 55008 KB Output is correct
4 Correct 66 ms 55120 KB Output is correct
5 Correct 60 ms 55376 KB Output is correct
6 Correct 61 ms 55120 KB Output is correct
7 Correct 88 ms 71496 KB Output is correct
8 Correct 84 ms 71236 KB Output is correct
9 Correct 79 ms 71072 KB Output is correct
10 Correct 58 ms 59972 KB Output is correct
11 Correct 80 ms 68164 KB Output is correct
12 Correct 59 ms 55376 KB Output is correct
13 Correct 77 ms 70980 KB Output is correct
14 Correct 80 ms 71476 KB Output is correct
15 Correct 85 ms 71132 KB Output is correct
16 Correct 79 ms 68228 KB Output is correct
17 Correct 69 ms 57028 KB Output is correct
18 Correct 60 ms 55436 KB Output is correct
19 Correct 1120 ms 353492 KB Output is correct
20 Correct 1116 ms 353328 KB Output is correct
21 Correct 1088 ms 352848 KB Output is correct
22 Correct 175 ms 86740 KB Output is correct
23 Correct 597 ms 186848 KB Output is correct
24 Correct 151 ms 62900 KB Output is correct
25 Correct 999 ms 352988 KB Output is correct
26 Correct 1000 ms 338200 KB Output is correct
27 Correct 1018 ms 338412 KB Output is correct
28 Correct 454 ms 171476 KB Output is correct
29 Correct 138 ms 70100 KB Output is correct
30 Correct 129 ms 62688 KB Output is correct
31 Correct 1217 ms 353212 KB Output is correct
32 Correct 1018 ms 353172 KB Output is correct
33 Correct 973 ms 353332 KB Output is correct
34 Correct 192 ms 86136 KB Output is correct
35 Correct 699 ms 187876 KB Output is correct
36 Correct 170 ms 62920 KB Output is correct
37 Correct 1179 ms 354000 KB Output is correct
38 Correct 1212 ms 353744 KB Output is correct
39 Correct 1193 ms 345300 KB Output is correct
40 Correct 446 ms 171732 KB Output is correct
41 Correct 124 ms 70100 KB Output is correct
42 Correct 119 ms 62692 KB Output is correct
43 Correct 1474 ms 689268 KB Output is correct
44 Correct 1735 ms 687212 KB Output is correct
45 Correct 1580 ms 686220 KB Output is correct
46 Correct 289 ms 178060 KB Output is correct
47 Correct 1113 ms 520572 KB Output is correct
48 Correct 154 ms 62680 KB Output is correct
49 Correct 1449 ms 688268 KB Output is correct
50 Correct 1579 ms 688420 KB Output is correct
51 Correct 1666 ms 688476 KB Output is correct
52 Correct 759 ms 503956 KB Output is correct
53 Correct 179 ms 105764 KB Output is correct