Submission #1097864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097864		vjudge1	Examination (JOI19_examination)	C++17	100 / 100	1735 ms	689268 KiB

examination

#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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57