oj.uz

Submission #1093535

# Submission time Handle Problem Language Result Execution time Memory
1093535 2024-09-27T02:43:17 Z Duckmannn Examination (JOI19_examination) C++17
43 / 100
 1490 ms 1048576 KB 
#include <bits/stdc++.h>

#define ll long long
#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 = 2e5 + 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 = 31; 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 = 31; 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[4 * 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 43 ms 44332 KB Output is correct
2 Correct 42 ms 44248 KB Output is correct
3 Correct 43 ms 44108 KB Output is correct
4 Correct 42 ms 44124 KB Output is correct
5 Correct 46 ms 44304 KB Output is correct
6 Correct 46 ms 44112 KB Output is correct
7 Correct 79 ms 80668 KB Output is correct
8 Correct 80 ms 79952 KB Output is correct
9 Correct 78 ms 79844 KB Output is correct
10 Correct 56 ms 53272 KB Output is correct
11 Correct 73 ms 74244 KB Output is correct
12 Correct 48 ms 44720 KB Output is correct
13 Correct 75 ms 79800 KB Output is correct
14 Correct 86 ms 79984 KB Output is correct
15 Correct 78 ms 80152 KB Output is correct
16 Correct 72 ms 74012 KB Output is correct
17 Correct 49 ms 47836 KB Output is correct
18 Correct 47 ms 44716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 668448 KB Output is correct
2 Correct 1255 ms 668088 KB Output is correct
3 Correct 1490 ms 668096 KB Output is correct
4 Correct 195 ms 103880 KB Output is correct
5 Correct 792 ms 339652 KB Output is correct
6 Correct 144 ms 58340 KB Output is correct
7 Correct 1386 ms 668472 KB Output is correct
8 Correct 1273 ms 632264 KB Output is correct
9 Correct 1205 ms 633288 KB Output is correct
10 Correct 497 ms 333992 KB Output is correct
11 Correct 122 ms 74436 KB Output is correct
12 Correct 113 ms 58268 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 668448 KB Output is correct
2 Correct 1255 ms 668088 KB Output is correct
3 Correct 1490 ms 668096 KB Output is correct
4 Correct 195 ms 103880 KB Output is correct
5 Correct 792 ms 339652 KB Output is correct
6 Correct 144 ms 58340 KB Output is correct
7 Correct 1386 ms 668472 KB Output is correct
8 Correct 1273 ms 632264 KB Output is correct
9 Correct 1205 ms 633288 KB Output is correct
10 Correct 497 ms 333992 KB Output is correct
11 Correct 122 ms 74436 KB Output is correct
12 Correct 113 ms 58268 KB Output is correct
13 Correct 1441 ms 668612 KB Output is correct
14 Correct 1453 ms 668868 KB Output is correct
15 Correct 1387 ms 668320 KB Output is correct
16 Correct 208 ms 103880 KB Output is correct
17 Correct 761 ms 341636 KB Output is correct
18 Correct 143 ms 58332 KB Output is correct
19 Correct 1372 ms 668620 KB Output is correct
20 Correct 1398 ms 668396 KB Output is correct
21 Correct 1479 ms 652232 KB Output is correct
22 Correct 486 ms 335048 KB Output is correct
23 Correct 123 ms 74440 KB Output is correct
24 Correct 112 ms 58340 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 44332 KB Output is correct
2 Correct 42 ms 44248 KB Output is correct
3 Correct 43 ms 44108 KB Output is correct
4 Correct 42 ms 44124 KB Output is correct
5 Correct 46 ms 44304 KB Output is correct
6 Correct 46 ms 44112 KB Output is correct
7 Correct 79 ms 80668 KB Output is correct
8 Correct 80 ms 79952 KB Output is correct
9 Correct 78 ms 79844 KB Output is correct
10 Correct 56 ms 53272 KB Output is correct
11 Correct 73 ms 74244 KB Output is correct
12 Correct 48 ms 44720 KB Output is correct
13 Correct 75 ms 79800 KB Output is correct
14 Correct 86 ms 79984 KB Output is correct
15 Correct 78 ms 80152 KB Output is correct
16 Correct 72 ms 74012 KB Output is correct
17 Correct 49 ms 47836 KB Output is correct
18 Correct 47 ms 44716 KB Output is correct
19 Correct 1399 ms 668448 KB Output is correct
20 Correct 1255 ms 668088 KB Output is correct
21 Correct 1490 ms 668096 KB Output is correct
22 Correct 195 ms 103880 KB Output is correct
23 Correct 792 ms 339652 KB Output is correct
24 Correct 144 ms 58340 KB Output is correct
25 Correct 1386 ms 668472 KB Output is correct
26 Correct 1273 ms 632264 KB Output is correct
27 Correct 1205 ms 633288 KB Output is correct
28 Correct 497 ms 333992 KB Output is correct
29 Correct 122 ms 74436 KB Output is correct
30 Correct 113 ms 58268 KB Output is correct
31 Correct 1441 ms 668612 KB Output is correct
32 Correct 1453 ms 668868 KB Output is correct
33 Correct 1387 ms 668320 KB Output is correct
34 Correct 208 ms 103880 KB Output is correct
35 Correct 761 ms 341636 KB Output is correct
36 Correct 143 ms 58332 KB Output is correct
37 Correct 1372 ms 668620 KB Output is correct
38 Correct 1398 ms 668396 KB Output is correct
39 Correct 1479 ms 652232 KB Output is correct
40 Correct 486 ms 335048 KB Output is correct
41 Correct 123 ms 74440 KB Output is correct
42 Correct 112 ms 58340 KB Output is correct
43 Runtime error 1356 ms 1048576 KB Execution killed with signal 9
44 Halted 0 ms 0 KB -