oj.uz

Submission #1093530

# Submission time Handle Problem Language Result Execution time Memory
1093530 2024-09-27T02:35:32 Z Duckmannn Examination (JOI19_examination) C++17
0 / 100
 1287 ms 625784 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 = 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 == 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, 2e9);
    }
  }

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 44116 KB Output is correct
2 Correct 45 ms 44280 KB Output is correct
3 Correct 44 ms 44124 KB Output is correct
4 Correct 44 ms 44124 KB Output is correct
5 Correct 44 ms 44320 KB Output is correct
6 Correct 44 ms 44116 KB Output is correct
7 Correct 77 ms 76316 KB Output is correct
8 Correct 82 ms 76044 KB Output is correct
9 Correct 77 ms 75544 KB Output is correct
10 Correct 52 ms 53784 KB Output is correct
11 Correct 70 ms 70168 KB Output is correct
12 Incorrect 49 ms 44720 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 44116 KB Output is correct
2 Correct 45 ms 44280 KB Output is correct
3 Correct 44 ms 44124 KB Output is correct
4 Correct 44 ms 44124 KB Output is correct
5 Correct 44 ms 44320 KB Output is correct
6 Correct 44 ms 44116 KB Output is correct
7 Correct 77 ms 76316 KB Output is correct
8 Correct 82 ms 76044 KB Output is correct
9 Correct 77 ms 75544 KB Output is correct
10 Correct 52 ms 53784 KB Output is correct
11 Correct 70 ms 70168 KB Output is correct
12 Incorrect 49 ms 44720 KB Output isn't correct
13 Halted 0 ms 0 KB -