oj.uz

Submission #1093533

# Submission time Handle Problem Language Result Execution time Memory
1093533 2024-09-27T02:40:41 Z Duckmannn Examination (JOI19_examination) C++17
0 / 100
 1272 ms 668100 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 == 1) {
        ll z = t[cur].nx[0];
        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 f, ll s, 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(s) - tree[id].get(f - 1);
  ll mid = (l + r) / 2;
  return get(st, en, f, s, id * 2, l, mid) + get(st, en, f, s, 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, (1ll << 32) - 1);
    }
  }

  fr(i, 1, q) cout<<kq[i]<<'\n'; 
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 44268 KB Output is correct
2 Correct 42 ms 44116 KB Output is correct
3 Correct 43 ms 44112 KB Output is correct
4 Correct 46 ms 44380 KB Output is correct
5 Correct 45 ms 44164 KB Output is correct
6 Correct 44 ms 44112 KB Output is correct
7 Correct 77 ms 80900 KB Output is correct
8 Correct 93 ms 79924 KB Output is correct
9 Correct 80 ms 79900 KB Output is correct
10 Correct 51 ms 53368 KB Output is correct
11 Correct 77 ms 74196 KB Output is correct
12 Incorrect 47 ms 44724 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1272 ms 668100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1272 ms 668100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 44268 KB Output is correct
2 Correct 42 ms 44116 KB Output is correct
3 Correct 43 ms 44112 KB Output is correct
4 Correct 46 ms 44380 KB Output is correct
5 Correct 45 ms 44164 KB Output is correct
6 Correct 44 ms 44112 KB Output is correct
7 Correct 77 ms 80900 KB Output is correct
8 Correct 93 ms 79924 KB Output is correct
9 Correct 80 ms 79900 KB Output is correct
10 Correct 51 ms 53368 KB Output is correct
11 Correct 77 ms 74196 KB Output is correct
12 Incorrect 47 ms 44724 KB Output isn't correct
13 Halted 0 ms 0 KB -