Submission #752034

#	Time	Username	Problem	Language	Result	Execution time	Memory
752034		NeroZein	Examination (JOI19_examination)	C++17	100 / 100	1727 ms	11572 KiB

examination

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int BL = 317; 
const int N = 100005;

struct Queries {
  int a, b, c, id;
  bool operator < (const Queries& other) {
    if (a / BL != other.a / BL) {
      return a < other.a; 
    }
    return b < other.b; 
  }; 
}; 

int tree[N];
inline void upd (int id, int v) {
  id++; 
  while (id < N) {
    tree[id] += v;
    id += id & -id;
  }
}

inline int qry (int id) {
  id++;
  int ret = 0;  
  while (id) {
    ret += tree[id];
    id -= id & -id;
  }
  return ret;
}

inline int qry (int l, int r) {
  return qry(r) - qry(l - 1); 
}

pair<int, int> a[N], b[N]; 
int c[N], A[N], B[N], C[N]; 
Queries qs[N]; 
int ans[N]; 
int cnt[N]; 

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; ++i) {
    cin >> a[i].first >> b[i].first;
    a[i].second = i;
    b[i].second = i;
    c[i] = a[i].first + b[i].first;
    A[i] = a[i].first;
    B[i] = b[i].first;
    C[i] = c[i];
  }
  sort(a, a + n);
  sort(A, A + n);
  sort(b, b + n);
  sort(B, B + n);
  sort(C, C + n);
  for (int i = 0; i < n; ++i) {
    a[i].first = i;
    b[i].first = i;
    c[i] = lower_bound(C, C + n, c[i]) - C;
  }
  for (int i = 0; i < q; ++i) {
    cin >> qs[i].a >> qs[i].b >> qs[i].c;
    qs[i].a = lower_bound(A, A + n, qs[i].a) - A; 
    qs[i].b = lower_bound(B, B + n, qs[i].b) - B; 
    qs[i].c = lower_bound(C, C + n, qs[i].c) - C; 
    qs[i].id = i; 
  }
  sort(qs, qs + q); 
  int pA = n, pB = n; 
  for (int i = 0; i < q; ++i) {
    while (pA - 1 >= 0 && a[pA - 1].first >= qs[i].a) {
      pA--; 
      ++cnt[a[pA].second];
      if (cnt[a[pA].second] == 2) {
        upd(c[a[pA].second], 1);
      }
    }
    while (pA < n && a[pA].first < qs[i].a) {
      --cnt[a[pA].second];
      if (cnt[a[pA].second] == 1) {
        upd(c[a[pA].second], -1);
      }
      pA++;
    }
    while (pB - 1 >= 0 && b[pB - 1].first >= qs[i].b) {
      pB--; 
      ++cnt[b[pB].second];
      if (cnt[b[pB].second] == 2) {
        upd(c[b[pB].second], 1);
      }
    }
    while (pB < n && b[pB].first < qs[i].b) {
      --cnt[b[pB].second];
      if (cnt[b[pB].second] == 1) {
        upd(c[b[pB].second], -1);
      }
      pB++; 
    }
    ans[qs[i].id] = qry(qs[i].c, n - 1); 
  }
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << "\n"; 
  }
  return 0;
}

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