#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;
}
};
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};
convs[a[i]];
convt[b[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++;
MAXX = cnt;
cnt = 0;
for(auto &p:convt) p.second = cnt++;
MAXY = cnt;
loop(i,0,n) s[i] = convs[s[i]], t[i] = convt[t[i]];
loop(i,0,q) a[i] = convs[a[i]], b[i] = convt[b[i]];*/
Node2d seg;
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);
}
else{ // query
i-=n;
ans[i] = seg.query(a[i], MAXX, b[i], MAXY, 0, MAXX);
}
}
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 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
1004 KB |
Output is correct |
5 |
Correct |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
280 ms |
166380 KB |
Output is correct |
8 |
Correct |
281 ms |
166380 KB |
Output is correct |
9 |
Correct |
293 ms |
166452 KB |
Output is correct |
10 |
Correct |
41 ms |
19948 KB |
Output is correct |
11 |
Correct |
40 ms |
18156 KB |
Output is correct |
12 |
Correct |
10 ms |
492 KB |
Output is correct |
13 |
Correct |
283 ms |
166508 KB |
Output is correct |
14 |
Correct |
280 ms |
166380 KB |
Output is correct |
15 |
Correct |
278 ms |
166508 KB |
Output is correct |
16 |
Correct |
27 ms |
7788 KB |
Output is correct |
17 |
Correct |
23 ms |
9708 KB |
Output is correct |
18 |
Correct |
9 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3150 ms |
963836 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3150 ms |
963836 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 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
1004 KB |
Output is correct |
5 |
Correct |
2 ms |
1004 KB |
Output is correct |
6 |
Correct |
2 ms |
1004 KB |
Output is correct |
7 |
Correct |
280 ms |
166380 KB |
Output is correct |
8 |
Correct |
281 ms |
166380 KB |
Output is correct |
9 |
Correct |
293 ms |
166452 KB |
Output is correct |
10 |
Correct |
41 ms |
19948 KB |
Output is correct |
11 |
Correct |
40 ms |
18156 KB |
Output is correct |
12 |
Correct |
10 ms |
492 KB |
Output is correct |
13 |
Correct |
283 ms |
166508 KB |
Output is correct |
14 |
Correct |
280 ms |
166380 KB |
Output is correct |
15 |
Correct |
278 ms |
166508 KB |
Output is correct |
16 |
Correct |
27 ms |
7788 KB |
Output is correct |
17 |
Correct |
23 ms |
9708 KB |
Output is correct |
18 |
Correct |
9 ms |
620 KB |
Output is correct |
19 |
Execution timed out |
3150 ms |
963836 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |