Submission #758787

#	Time	Username	Problem	Language	Result	Execution time	Memory
758787		mgl_diamond	Examination (JOI19_examination)	C++14	100 / 100	995 ms	329880 KiB

examination

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l; i>=(r); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define fi first
#define se second
#define C make_pair
 
using dt = pair<ii, int>;
const int N = 2e5+5;
const int INF = 1e9;
const int SQRT = sqrt(N);

int debug = 0;

struct trie {
  struct node {
    int nxt[2], cnt = 0;
    node() { nxt[0] = nxt[1] = -1; cnt = 0; }
  };

  vector<node> trie;

  void built() {
    trie.push_back(node());
  }

  void add(int num) {
    for(int i=30, cur=0; i>=0; --i) {
      int bit = num>>i&1;
      if (trie[cur].nxt[bit] == -1) {
        trie[cur].nxt[bit] = trie.size();
        trie.push_back(node());
      } 
      cur = trie[cur].nxt[bit];
      trie[cur].cnt += 1;
    }
  }

  int query(int val) {
    int ans = 0, cur = 0;
    for(int i=30; i>=0; --i) {
      int bit = val>>i&1;
      if (bit == 1) cur = trie[cur].nxt[1];
      else {
        if (trie[cur].nxt[1] != -1) ans += trie[trie[cur].nxt[1]].cnt;
        cur = trie[cur].nxt[0];
      }
      if (cur == -1) return ans;
    }
    assert(cur != -1);
    return ans + trie[cur].cnt;
  }
};

int n, ny, q, ret[N];
int qx[N], qy[N], qz[N];
vector<int> vy;
vector<ii> a(N);
vector<dt> evts;
vector<trie> bit(N);

bool cmp(dt a, dt b) {
  if (a.fi.fi != b.fi.fi) return a.fi.fi > b.fi.fi;
  return a.se < b.se;
}

int pos(int val) {
  int id = upper_bound(all(vy), val) - vy.begin();
  return id;
}

void upd(int i, int v) {
  for(i=ny-i+1; i<=ny; i+=i&-i) bit[i].add(v);
}

int query(int i, int v) {
  int ans = 0;
  for(i=ny-i+1; i>0; i-=i&-i) ans += bit[i].query(v);
  return ans;
}

void solve() {
  cin >> n >> q;

  for(int i=1; i<=n; ++i) {
    cin >> a[i].fi >> a[i].se;
    vy.push_back(a[i].se);
    evts.push_back(C(C(a[i].fi, i), 0));
  }

  for(int i=1; i<=q; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    qx[i] = x; qy[i] = y; qz[i] = z;
    vy.push_back(y);
    evts.push_back(C(C(x, i), 1));
  } 

  sort(all(evts), cmp);
  sort(all(vy));
  vy.resize(unique(all(vy)) - vy.begin());
  ny = vy.size();

  // for(int x : vy) cout << x << " ";
  // cout << "\n";

  for(int i=0; i<=ny; ++i) {
    bit[i].built();
  }

  // upd(3, 120);
  // upd(6, 140);
  // cout << bit[3].query(80);
  // cout << query(5, 80) << "\n";

  for(auto e : evts) {
    // cout << pos(10) << "\n";
    // cout << e.fi.fi << " " << e.se << "\n";
    if (e.se == 0) {
      int i = e.fi.se;
      upd(pos(a[i].se), a[i].fi + a[i].se);
      // cout << "update pos " << pos(a[i].se) << " value " << a[i].fi + a[i].se << "\n";
    } else {
      int i = e.fi.se;
      int val = qx[i] + qy[i] + max(0, qz[i] - (qx[i] + qy[i]));
      // assert(pos(qy[i]) <= ny);
      ret[i] = query(pos(qy[i]), val);
      // cout << "query pos " << pos(qy[i]) << " greater than " << val << "\n";
    }
  }

  for(int i=1; i<=q; ++i) {
    cout << ret[i] << "\n";
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
 
  if (fopen("input.inp", "r")) {
    freopen("input.inp", "r", stdin);
    freopen("input.out", "w", stdout);
  }
 
  solve();
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:148:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:149:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |     freopen("input.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57