#include <bits/stdc++.h>
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
using namespace std;
const int INF = 1e9, MOD = 1e9 + 7;
int MAXX = 0, MAXY = 0;
struct Node{
int v=0;
Node *lp=0, *rp=0;
Node(){}
void fix(){
if (!lp) lp = new Node();
if (!rp) rp = new Node();
}
void update(int i, int dx, int l, int r){
if (r<=l) return ;
if (l+1==r){
v+=dx;
return ;
}
int mid = (l+r)/2;
fix();
if (i<mid) lp->update(i,dx,l,mid);
else rp->update(i,dx,mid,r);
//cout<<"UPDATE1: "<<i<<" "<<l<<" "<<r<<(v - lp->v - rp->v)<<endl;
v = lp->v + rp->v;
}
int query(int a, int b, int l, int r){
if (a>r || b<l) return 0;
//cout<<"QUERY1: "<<a<<" "<<v<<" "<<l<<" "<<r<<endl;
if (a<=l && r<=b) return v;
int res = 0, mid = (l+r)/2;
if (lp) res += lp->query(a,b,l,mid);
if (rp) res += rp->query(a,b,mid,r);
return res;
}
};
struct Node2d{
Node seg;
Node2d *lp=0, *rp=0;
Node2d(){}
void fix(){
if (!lp) lp = new Node2d();
if (!rp) rp = new Node2d();
}
void update(int i, int j, int dx, int l, int r){
if (r<=l) return ;
//cout<<"UPDATE: "<<i<<" "<<j<<" "<<l<<" "<<r<<endl;
seg.update(j, dx, 0, MAXY);
if (l+1==r) return ;
int mid = (l+r)/2;
fix();
if (i<mid) lp->update(i,j,dx,l,mid);
else rp->update(i,j,dx,mid,r);
}
int query(int ax, int bx, int ay, int by, int l, int r){
if (ax>r || bx<l) return 0;
if (ax<=l && r<=bx) {
int v = seg.query(ay, by, 0, MAXY);
//cout<<"QUERY: "<<ax<<" "<<ay<<" "<<l<<" "<<r<<" "<<v<<endl;
return v;
}
int res = 0, mid = (l+r)/2;
if (lp) res += lp->query(ax,bx,ay,by,l,mid);
if (rp) res += rp->query(ax,bx,ay,by,mid,r);
return res;
}
};
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
const int RANDOM =
chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
int operator()(int x) const { return x ^ RANDOM; }
};
struct sparsebit {
const int MAX = 1e5+10;
vector<gp_hash_table<int, int, chash>> fen;
sparsebit(): fen(MAX+1){}
int tot = 0;
void add(int x, int y) {
// debug("in upd");
tot++;
for (int i = x; i <= MAX; i += (i & -i)) {
for (int j = y; j <= MAX; j += (j & -j)) {
// debug(i, j, 1);
// cnt++;
fen[i][j] ++;
}
}
// debug("out upd");
}
int qry(int x, int y) {
int ret = 0;
for (int i = x; i > 0; i -= (i & -i)) {
for (int j = y; j > 0; j -= (j & -j)) {
// cnt++;
ret += fen[i][j];
}
}
return ret;
}
int qry(int a, int b, int c, int d) {
// debug("in big qry");
int ret = tot;
if (a) ret -= qry(a - 1, d);
if (b) ret -= qry(c, b - 1);
if (a && b) ret += qry(a - 1, b - 1);
// debug("out big qry");
return ret;
}
void init() { fen.resize(MAX + 1); }
};*/
bool cmp(pair<int, int> a, pair<int, int> b){
return (a.first==b.first?a.second<b.second:a.first>b.first);
}
const int MAXN = 1e5 + 10;
int s[MAXN], t[MAXN];
int a[MAXN], b[MAXN], c[MAXN];
int ans[MAXN];
pair<int, int> vals[2*MAXN];
int32_t main(){
ios_base::sync_with_stdio(false);
int n,q; cin>>n>>q;
map<int, int> convs, convt;
loop(i,0,n){
cin>>s[i]>>t[i];
vals[i] = {s[i]+t[i], i};
convs[s[i]];
convt[t[i]];
//MAXX = max(MAXX, s[i]);
//MAXY = max(MAXY, t[i]);
}
loop(i,0,q){
cin>>a[i]>>b[i]>>c[i];
vals[i+n] = {c[i], n+i};
//MAXX = max(MAXX, a[i]);
//MAXY = max(MAXY, b[i]);
}
sort(vals, vals+n+q, cmp);
//MAXX++, MAXY++;
int cnt = 0;
for(auto &p:convs) p.second = cnt++;
for(auto &p:convs) p.second = cnt - p.second;
MAXX = cnt;
cnt = 0;
for(auto &p:convt) p.second = cnt++;
for(auto &p:convt) p.second = cnt - p.second;
MAXY = cnt;
loop(i,0,n) s[i] = convs[s[i]], t[i] = convt[t[i]];
loop(i,0,q) a[i] = convs.lower_bound(a[i])->second, b[i] = convt.lower_bound(b[i])->second;
Node2d seg;
//sparsebit bit;
loop(ind, 0, n+q){
int i = vals[ind].second;
//cout<<"VALS: "<<vals[ind].first<<" "<<i<<" "<<i-n<<endl;
if (i<n){ // point
seg.update(s[i], t[i], 1, 0, MAXX);
//bit.add(s[i], t[i]);
}
else{ // query
i-=n;
ans [i] = seg.query(0, a[i]+1, 0, b[i]+1, 0, MAXX);
//ans[i] = bit.qry(a[i], b[i]);
}
}
loop(i,0,q) cout<<ans[i]<<endl;
return 0;
}
/*
color a
cls
g++ Examination.cpp -o a & a
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3140 ms |
820228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3140 ms |
820228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
