제출 #231328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231328		AlexLuchianov	Examination (JOI19_examination)	C++14	100 / 100	2679 ms	152248 KiB

examination

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <map>
#include <random>

using namespace std;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

mt19937 rng;
int const nmax = 200000;
int const inf = 1000000000;

int _random(){
  return uniform_int_distribution<int>(inf)(rng);
}

class Treap{
public:
  struct Node{
    int val;
    int sz;
    int prio;
    Node* left;
    Node* right;
    Node(int val_){
      val = val_;
      sz = 1;
      prio = _random();
      left = right = nullptr;
    }
  };

  int getsize(Node* &root){
    if(root == nullptr)
      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 == nullptr)
      return {nullptr, nullptr};
    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 == nullptr && b == nullptr)
      return nullptr;
    else if(a == nullptr)
      return b;
    else if(b == nullptr)
      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 = nullptr;
  }
  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 result = getsize(sol.second);
    root = _merge(sol.first, sol.second);
    return result;
  }
};

struct Event{
  int type;
  int x, y, z;
  int id;
  bool operator < (Event const &a) const {
    if(x != a.x)
      return a.x < x;
    else
      return type < a.type;
  }
};
vector<Event> events;
int sol[1 + nmax];
map<int,int> code;

int normalize(){
  vector<int> temp;
  for(int i = 0; i < events.size(); i++){
    temp.push_back(events[i].x);
    temp.push_back(events[i].y);
    temp.push_back(events[i].z);
  }
  sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  for(int i = 0; i < temp.size(); i++)
    code[temp[i]] = 1 + i;
  for(int i = 0; i < events.size(); i++) {
    events[i].x = code[events[i].x];
    events[i].y = code[events[i].y];
    events[i].z = code[events[i].z];
  }
  return temp.size();
}

class SegmentTree{
private:
  vector<Treap> aint;
public:
  SegmentTree(int n){
    aint.resize(1 + 4 * n);
  }
  void update(int node, int from, int to, int x, int y){
    aint[node]._insert(y);
    if(from < to){
      int mid = (from + to) / 2;
      if(x <= mid)
        update(node * 2, from, mid, x, y);
      else if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, x, y);
    }
  }

  int query(int node, int from, int to, int x, int x2, int y){
    if(from == x && to == x2)
      return aint[node]._query(y);
    else {
      int mid = (from + to) / 2;
      if(x <= mid && x2 <= mid)
        return query(node * 2, from, mid, x, x2, y);
      else if(mid + 1 <= x && mid + 1 <= x2)
        return query(node * 2 + 1, mid + 1, to, x, x2, y);
      else
        return query(node * 2, from, mid, x, mid, y) +
               query(node * 2 + 1, mid + 1, to, mid + 1, x2, y);
    }
  }
};

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, q;
  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());
  int lim = normalize();
  SegmentTree aint(lim);

  for(int i = 0; i < events.size(); i++){
    int x = events[i].y;
    int y = events[i].z;
    if(events[i].type == 1)
      aint.update(1, 1, lim, x, y);
    else
      sol[events[i].id] = aint.query(1, 1, lim, x, lim, y);
  }
  for(int i = 1; i <= q; i++)
    cout << sol[i] << '\n';
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int normalize()':
examination.cpp:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < events.size(); i++){
                  ~~^~~~~~~~~~~~~~~
examination.cpp:125:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++)
                  ~~^~~~~~~~~~~~~
examination.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < events.size(); i++) {
                  ~~^~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:190:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < events.size(); i++){
                  ~~^~~~~~~~~~~~~~~

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