//
// ROIGold.cpp
// Main calisma
//
// Created by Rakhman on 05/02/2019.
// Copyright © 2019 Rakhman. All rights reserved.
//
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)
const long long MXN = 2e5 + 10;
const long long MNN = 1e6 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e16;
const long long OO = 1e9 + 10;
typedef long long llong;
typedef unsigned long long ullong;
using namespace std;
void istxt(bool yes){
if(yes == 1){
freopen("balancing.in", "r", stdin);
freopen("balancing.out", "w", stdout);
}else{
freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
}
}
int n, q, ans[MXN];
vector<int> ys, xs;
struct lol{
int a, b, c, ind;
}p[MXN], t[MXN];
bool cmp(lol a, lol b){
return a.c < b.c;
}
struct node{
node *l, *r, *y;
int sum = 0;
node(){
l = r = y = nullptr;
sum = 0;
}
};
typedef node* pnode;
int getsum(pnode a) { return (a == nullptr ? 0 : a -> sum); }
int gety(pnode &vy, int tl, int tr, int L, int R){
if(vy == nullptr) return 0;
if(L <= tl && tr <= R){
return vy -> sum;
}
if(R < tl || tr < L){
return 0;
}
int tm = (tl + tr) / 2;
return gety(vy -> l, tl, tm, L, R) + gety(vy -> r, tm + 1, tr, L, R);
}
int getx(pnode &v, int tl, int tr, int lx, int rx, int ly, int ry){
if(v == nullptr) return 0;
if(lx <= tl && tr <= rx){
return gety(v -> y, 0, ys.size(), ly, ry);
}
if(rx < tl || tr < lx){
return 0;
}
int tm = (tl + tr) / 2;
return getx(v -> l, tl, tm, lx, rx, ly, ry) + getx(v -> r, tm + 1, tr, lx, rx, ly, ry);
}
void updy(pnode &vy, pnode lv, pnode rv, int lx, int rx, int tl, int tr, int posy, int x){
if(vy == nullptr) vy = new node();
if(tl == tr){
if(lx == rx){
vy -> sum += x;
}else{
vy -> sum = getsum(lv) + getsum(rv);
}
}else{
int tm = (tl + tr) / 2;
if(posy <= tm){
updy(vy -> l, (lv == nullptr ? nullptr : lv -> l), (rv == nullptr ? nullptr : rv -> l), lx, rx, tl, tm, posy, x);
}else{
updy(vy -> r, (lv == nullptr ? nullptr : lv -> r), (rv == nullptr ? nullptr : rv -> r), lx, rx, tm + 1, tr, posy, x);
}
vy -> sum = getsum(vy -> r) + getsum(vy -> l);
}
}
void updx(pnode &v, int tl, int tr, int posx, int posy, int x){
if(v == nullptr){
v = new node();
}
if(tl == tr){
updy(v -> y, nullptr, nullptr, tl, tr, 0, ys.size() - 1, posy, x);
//cout << (v -> y) -> sum << nl;
return ;
}
int tm = (tl + tr) / 2;
if(posx <= tm){
updx(v -> l, tl, tm, posx, posy, x);
}else{
updx(v -> r, tm + 1, tr, posx, posy, x);
}
updy(v -> y, (v -> l == nullptr ? nullptr : (v -> l) -> y), (v -> r == nullptr ? nullptr : (v -> r) -> y), tl, tr, 0, ys.size() - 1, posy, x);
}
pnode rootx = new node();
int main () {
ios;
//istxt(0);
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> p[i].a >> p[i].b;
p[i].ind = i;
p[i].c = p[i].a + p[i].b;
xs.push_back(p[i].a);
ys.push_back(p[i].b);
}
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
xs.push_back(1e9);
ys.push_back(1e9);
xs.erase(unique(xs.begin(), xs.end()), xs.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
for(int i = 1; i <= n; i++){
p[i].a = lower_bound(xs.begin(), xs.end(), p[i].a) - xs.begin();
p[i].b = lower_bound(ys.begin(), ys.end(), p[i].b) - ys.begin();
updx(rootx, 0, xs.size() - 1, p[i].a, p[i].b, 1);
}
sort(p + 1, p + n + 1, cmp);
for(int i = 1; i <= q; i++){
cin >> t[i].a >> t[i].b >> t[i].c;
t[i].ind = i;
}
sort(t + 1, t + q + 1, cmp);
int cnt = 1;
for(int i = 1; i <= q; i++){
while(cnt <= n && t[i].c > p[cnt].c){
updx(rootx, 0, xs.size() - 1, p[cnt].a, p[cnt].b, -1);
cnt++;
}
if(cnt > n) ans[t[i].ind] = 0;
else{
int a = lower_bound(xs.begin(), xs.end(), t[i].a) - xs.begin();
int b = lower_bound(ys.begin(), ys.end(), t[i].b) - ys.begin();
ans[t[i].ind] = getx(rootx, 0, xs.size() - 1, a, xs.size() - 1, b, ys.size() - 1);
}
}
for(int i = 1; i <= q; i++){
cout << ans[i] << nl;
}
}
Compilation message
examination.cpp: In function 'void istxt(bool)':
examination.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("balancing.in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("balancing.out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3114 ms |
689584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3114 ms |
689584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
