Submission #855883

#	Time	Username	Problem	Language	Result	Execution time	Memory
855883		rxlfd314	Examination (JOI19_examination)	C++17	100 / 100	1399 ms	275488 KiB

examination

// haha lol wtf am I doing
#include <bits/stdc++.h>
using namespace std;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)

struct ST {
  int val;
  ST *lft, *rht;
  ST() : lft(nullptr), rht(nullptr), val(0) {}
  void upd(int p, int v, int tl, int tr) {
    if (tl == tr)
      val += v;
    else {
      int tm = tl + tr >> 1;
      if (p > tm) {
        if (!rht)
          rht = new ST();
        rht->upd(p, v, tm+1, tr);
      } else {
        if (!lft)
          lft = new ST();
        lft->upd(p, v, tl, tm);
      } 
      val = (lft ? lft->val : 0) + (rht ? rht->val : 0);
    }
  }
  int qry(int ql, int qr, int tl, int tr) {
    if (tl > qr || tr < ql)
      return 0;
    if (ql <= tl && tr <= qr)
      return val;
    int tm = tl + tr >> 1;
    return (lft ? lft->qry(ql, qr, tl, tm) : 0) + (rht ? rht->qry(ql, qr, tm+1, tr) : 0);
  }
};

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int N, Q;
  cin >> N >> Q;
  array<int, 5> evs[N+Q];
  vt<int> cpa, cpb;
  FOR(i, 0, N-1) {
    int a, b;
    cin >> a >> b;
    cpa.push_back(a);
    cpb.push_back(b);
    evs[i] = {a + b, a, b, -1, -1};
  }
  
  FOR(i, 0, Q-1) {
    int x, y, z;
    cin >> x >> y >> z;
    evs[N+i] = {z, -1, x, y, i};
  }
  
  sort(evs, evs+N+Q);
  
  sort(all(cpa));
  cpa.erase(unique(all(cpa)), end(cpa));
  auto ind_a = [&](int v) {
    return int(lower_bound(all(cpa), v) - begin(cpa));
  };
  
  sort(all(cpb));
  cpb.erase(unique(all(cpb)), end(cpb));
  auto ind_b = [&](int v) {
    return int(lower_bound(all(cpb), v) - begin(cpb));
  };
  
  vt<ST> sgt(size(cpa), ST());
  auto upd = [&](int a, int b, int v) {
    a = ind_a(a), b = ind_b(b);
    for (; a < size(cpa); a += a+1 & -a-1)
      sgt[a].upd(b, v, 0, size(cpb)-1);
  };
  auto p_qry = [&](int i, int l, int r) {
    int ret = 0;
    for (; ~i; i -= i+1 & -i-1)
      ret += sgt[i].qry(l, r, 0, size(cpb)-1);
    return ret;
  };
  auto qry = [&](int a, int b, int c, int d) {
    a = ind_a(a), b = min(ind_a(b), size(cpa)-1), c = ind_b(c), d = ind_b(d);
    return p_qry(b, c, d) - p_qry(a-1, c, d);
  };
  FOR(i, 0, N+Q-1)
    if (~evs[i][1])
      upd(evs[i][1], evs[i][2], 1);
 
  int ans[Q];
  FOR(i, 0, N+Q-1) {
    if (~evs[i][1])
      upd(evs[i][1], evs[i][2], -1);
    else
      ans[evs[i][4]] = qry(evs[i][2], INT_MAX, evs[i][3], INT_MAX);
  }
  
  FOR(i, 0, Q-1)
    cout << ans[i] << '\n';
}

Compilation message (stderr)

examination.cpp: In constructor 'ST::ST()':
examination.cpp:18:13: warning: 'ST::rht' will be initialized after [-Wreorder]
   18 |   ST *lft, *rht;
      |             ^~~
examination.cpp:17:7: warning:   'int ST::val' [-Wreorder]
   17 |   int val;
      |       ^~~
examination.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   ST() : lft(nullptr), rht(nullptr), val(0) {}
      |   ^~
examination.cpp: In member function 'void ST::upd(int, int, int, int)':
examination.cpp:24:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
examination.cpp: In member function 'int ST::qry(int, int, int, int)':
examination.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
examination.cpp: In lambda function:
examination.cpp:86:33: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   86 |     for (; a < size(cpa); a += a+1 & -a-1)
      |                                ~^~
examination.cpp: In lambda function:
examination.cpp:91:22: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   91 |     for (; ~i; i -= i+1 & -i-1)
      |                     ~^~

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