oj.uz

Submission #231328

# Submission time Handle Problem Language Result Execution time Memory
231328 2020-05-13T11:21:01 Z AlexLuchianov Examination (JOI19_examination) C++14
100 / 100
 2679 ms 152248 KB 
#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;
}

Compilation message

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 28 ms 4244 KB Output is correct
8 Correct 27 ms 4240 KB Output is correct
9 Correct 27 ms 4240 KB Output is correct
10 Correct 23 ms 3584 KB Output is correct
11 Correct 26 ms 3608 KB Output is correct
12 Correct 15 ms 1304 KB Output is correct
13 Correct 27 ms 3864 KB Output is correct
14 Correct 34 ms 3984 KB Output is correct
15 Correct 25 ms 3992 KB Output is correct
16 Correct 22 ms 2968 KB Output is correct
17 Correct 21 ms 3480 KB Output is correct
18 Correct 8 ms 920 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1703 ms 103480 KB Output is correct
2 Correct 1648 ms 103280 KB Output is correct
3 Correct 1635 ms 103404 KB Output is correct
4 Correct 836 ms 97700 KB Output is correct
5 Correct 1878 ms 97308 KB Output is correct
6 Correct 434 ms 32304 KB Output is correct
7 Correct 1611 ms 103000 KB Output is correct
8 Correct 1613 ms 103036 KB Output is correct
9 Correct 1516 ms 102312 KB Output is correct
10 Correct 1821 ms 95912 KB Output is correct
11 Correct 745 ms 98088 KB Output is correct
12 Correct 153 ms 20008 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1703 ms 103480 KB Output is correct
2 Correct 1648 ms 103280 KB Output is correct
3 Correct 1635 ms 103404 KB Output is correct
4 Correct 836 ms 97700 KB Output is correct
5 Correct 1878 ms 97308 KB Output is correct
6 Correct 434 ms 32304 KB Output is correct
7 Correct 1611 ms 103000 KB Output is correct
8 Correct 1613 ms 103036 KB Output is correct
9 Correct 1516 ms 102312 KB Output is correct
10 Correct 1821 ms 95912 KB Output is correct
11 Correct 745 ms 98088 KB Output is correct
12 Correct 153 ms 20008 KB Output is correct
13 Correct 2053 ms 107124 KB Output is correct
14 Correct 1877 ms 103976 KB Output is correct
15 Correct 1735 ms 103324 KB Output is correct
16 Correct 1076 ms 98316 KB Output is correct
17 Correct 2141 ms 97988 KB Output is correct
18 Correct 454 ms 32392 KB Output is correct
19 Correct 2202 ms 107184 KB Output is correct
20 Correct 2207 ms 105364 KB Output is correct
21 Correct 2542 ms 107000 KB Output is correct
22 Correct 1920 ms 95752 KB Output is correct
23 Correct 778 ms 98116 KB Output is correct
24 Correct 147 ms 20040 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 28 ms 4244 KB Output is correct
8 Correct 27 ms 4240 KB Output is correct
9 Correct 27 ms 4240 KB Output is correct
10 Correct 23 ms 3584 KB Output is correct
11 Correct 26 ms 3608 KB Output is correct
12 Correct 15 ms 1304 KB Output is correct
13 Correct 27 ms 3864 KB Output is correct
14 Correct 34 ms 3984 KB Output is correct
15 Correct 25 ms 3992 KB Output is correct
16 Correct 22 ms 2968 KB Output is correct
17 Correct 21 ms 3480 KB Output is correct
18 Correct 8 ms 920 KB Output is correct
19 Correct 1703 ms 103480 KB Output is correct
20 Correct 1648 ms 103280 KB Output is correct
21 Correct 1635 ms 103404 KB Output is correct
22 Correct 836 ms 97700 KB Output is correct
23 Correct 1878 ms 97308 KB Output is correct
24 Correct 434 ms 32304 KB Output is correct
25 Correct 1611 ms 103000 KB Output is correct
26 Correct 1613 ms 103036 KB Output is correct
27 Correct 1516 ms 102312 KB Output is correct
28 Correct 1821 ms 95912 KB Output is correct
29 Correct 745 ms 98088 KB Output is correct
30 Correct 153 ms 20008 KB Output is correct
31 Correct 2053 ms 107124 KB Output is correct
32 Correct 1877 ms 103976 KB Output is correct
33 Correct 1735 ms 103324 KB Output is correct
34 Correct 1076 ms 98316 KB Output is correct
35 Correct 2141 ms 97988 KB Output is correct
36 Correct 454 ms 32392 KB Output is correct
37 Correct 2202 ms 107184 KB Output is correct
38 Correct 2207 ms 105364 KB Output is correct
39 Correct 2542 ms 107000 KB Output is correct
40 Correct 1920 ms 95752 KB Output is correct
41 Correct 778 ms 98116 KB Output is correct
42 Correct 147 ms 20040 KB Output is correct
43 Correct 2567 ms 152248 KB Output is correct
44 Correct 2547 ms 152156 KB Output is correct
45 Correct 2333 ms 152232 KB Output is correct
46 Correct 1180 ms 131812 KB Output is correct
47 Correct 2442 ms 131484 KB Output is correct
48 Correct 581 ms 38184 KB Output is correct
49 Correct 2614 ms 152148 KB Output is correct
50 Correct 2575 ms 152100 KB Output is correct
51 Correct 2679 ms 152012 KB Output is correct
52 Correct 2323 ms 122256 KB Output is correct
53 Correct 807 ms 112532 KB Output is correct