oj.uz

Submission #1093529

# Submission time Handle Problem Language Result Execution time Memory
1093529 2024-09-27T02:34:39 Z Duckmannn Examination (JOI19_examination) C++17
0 / 100
 906 ms 341976 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 = 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 37 ms 44112 KB Output is correct
2 Correct 40 ms 44152 KB Output is correct
3 Correct 38 ms 44220 KB Output is correct
4 Correct 45 ms 44112 KB Output is correct
5 Correct 48 ms 44112 KB Output is correct
6 Correct 46 ms 44120 KB Output is correct
7 Correct 64 ms 60484 KB Output is correct
8 Correct 70 ms 60232 KB Output is correct
9 Correct 65 ms 60008 KB Output is correct
10 Correct 49 ms 48964 KB Output is correct
11 Correct 63 ms 57160 KB Output is correct
12 Incorrect 46 ms 44636 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 44112 KB Output is correct
2 Correct 40 ms 44152 KB Output is correct
3 Correct 38 ms 44220 KB Output is correct
4 Correct 45 ms 44112 KB Output is correct
5 Correct 48 ms 44112 KB Output is correct
6 Correct 46 ms 44120 KB Output is correct
7 Correct 64 ms 60484 KB Output is correct
8 Correct 70 ms 60232 KB Output is correct
9 Correct 65 ms 60008 KB Output is correct
10 Correct 49 ms 48964 KB Output is correct
11 Correct 63 ms 57160 KB Output is correct
12 Incorrect 46 ms 44636 KB Output isn't correct
13 Halted 0 ms 0 KB -