| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 231326 | AlexLuchianov | Examination (JOI19_examination) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <map>
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;
}