Submission #777258

#	Time	Username	Problem	Language	Result	Execution time	Memory
777258		tvladm2009	Examination (JOI19_examination)	C++17	100 / 100	1706 ms	123912 KiB

examination

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 1e5 + 7;
const int INF = (int) 1e9;

mt19937 rng;

int gen() {
  return uniform_int_distribution<int>(INF)(rng);
}

struct treap {
  struct node {
    int val;
    int sz;
    int prio;
    node* left;
    node* right;

    node(int val_ = 0) {
      val = val_;
      sz = 1;
      prio = gen();
      left = NULL;
      right = NULL;
    }
  };

  int getsize(node* &root) {
    if (root == NULL) {
      return 0;
    } else {
      return root->sz;
    }
  }

  void computesize(node* &root) {
    root->sz = 1 + getsize(root->left) + getsize(root->right);
  }

  pair<node*, node*> split(node* &root, int target) {
    if (root == NULL) {
      return {NULL, NULL};
    } else if (root->val <= target) {
      pair<node*, node*> sol = split(root->right, target);
      root->right = sol.first;
      computesize(root);
      return {root, sol.second};
    } else {
      pair<node*, node*> sol = split(root->left, target);
      root->left = sol.second;
      computesize(root);
      return {sol.first, root};
    }
  }

  node* _merge(node* &a, node* &b) {
    if (a == NULL && b == NULL) {
      return NULL;
    } else if (a == NULL) {
      return b;
    } else if (b == NULL) {
      return a;
    } else if (a->prio < b->prio) {
      a->right = _merge(a->right, b);
      computesize(a);
      return a;
    } else {
      b->left = _merge(a, b->left);
      computesize(b);
      return b;
    }
  }

  node* root;
  treap() {
    root = NULL;
  }
  void _insert(int val) {
    pair<node*, node*> sol = split(root, val);
    node* newnode = new node(val);
    sol.first = _merge(sol.first, newnode);
    root = _merge(sol.first, sol.second);
  }
  int _query(int val) {
    pair<node*, node*> sol = split(root, val - 1);
    int ret = getsize(sol.second);
    root = _merge(sol.first, sol.second);
    return ret;
  }
};

struct T {
  int type;
  int x, y, z;
  int id;
};

bool operator < (const T &a, const T &b) {
  if (a.x != b.x) {
    return a.x > b.x;
  } else {
    return a.type < b.type;
  }
}

vector<T> events;
int sol[N];
int n, q;

struct segtree {
  vector<treap> segt;

  segtree(int n) {
    segt.resize(4 * n + 1);
  }

  void update(int v, int tl, int tr, int x, int val) {
    segt[v]._insert(val);
    if (tl == tr) {
      return;
    }
    int tm = (tl + tr) / 2;
    if (x <= tm) {
      update(2 * v, tl, tm, x, val);
    } else {
      update(2 * v + 1, tm + 1, tr, x, val);
    }
  }

  int query(int v, int tl, int tr, int x, int y, int val) {
    if (x <= tl && tr <= y) {
      return segt[v]._query(val);
    } else {
      int tm = (tl + tr) / 2;
      if (x <= tm & y <= tm) {
        return query(2 * v, tl, tm, x, y, val);
      } else if (tm + 1 <= x && tm + 1 <= y) {
        return query(2 * v + 1, tm + 1, tr, x, y, val);
      } else {
        return query(2 * v, tl, tm, x, tm, val) + query(2 * v + 1, tm + 1, tr, tm + 1, y, val);
      }
    }
  }
};

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  // freopen("input", "r", stdin);

  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    int x, y;
    cin >> x >> y;
    events.push_back({1, x, y, x + y, i});
  }
  for (int i = 1; i <= q; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    events.push_back({2, x, y, z, i});
  }
  sort(events.begin(), events.end());
  {
    vector<int> vals;
    for (auto &e : events) {
      vals.push_back(e.x);
      vals.push_back(e.y);
      vals.push_back(e.z);
    }
    sort(vals.begin(), vals.end());
    map<int, int> mp;
    int cnt = 0;
    for (auto &i : vals) {
      if (mp[i] == 0) {
        mp[i] = ++cnt;
      }
    }
    for (auto &e : events) {
      e.x = mp[e.x];
      e.y = mp[e.y];
      e.z = mp[e.z];
    }
    n = cnt;
  }
  segtree tree(n);
  for (auto &e : events) {
    if (e.type == 1) {
      tree.update(1, 1, n, e.y, e.z);
    } else {
      sol[e.id] = tree.query(1, 1, n, e.y, n, e.z);
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << sol[i] << " ";
  }
  return 0;
}

Compilation message (stderr)

examination.cpp: In member function 'int segtree::query(int, int, int, int, int, int)':
examination.cpp:139:13: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  139 |       if (x <= tm & y <= tm) {
      |           ~~^~~~~

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