#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll
int n, m, k, a[300010], q, l, r;
struct n2{
n2 *l, *r;
int sum;
n2(){
this->l=this->r=NULL;
this->sum=0;
}
};
struct n1{
n1 *l, *r;
n2 *t2;
n1(){
this->l=this->r=NULL;
this->t2=NULL;
}
} *t1;
void update2( n2*&t, int l2, int r2, int y){
if(!t){
t=new n2();
}
if(l2==r2){
t->sum++;
return;
}
int mid=(l2+r2)>>1ll;
if(y<=mid){
update2(t->l, l2, mid, y);
}
else{
update2(t->r, mid+1, r2, y);
}
t->sum++;
}
void update1(n1 *&t, int l1, int r1, int l2, int r2, int x, int y){
if(!t){
t=new n1();
}
update2(t->t2, l2, r2, y);
if(l1==r1){
return;
}
int mid=(l1+r1)>>1ll;
if(x<=mid){
update1(t->l, l1, mid, l2, r2, x, y);
}
else{
update1(t->r, mid+1, r1, l2, r2, x, y);
}
return;
}
int query2(n2 *t, int l2, int r2, int y1, int y2){
if(!t){
return 0;
}
if(y1>y2){
return 0;
}
if( (y1==l2) && (y2==r2) ){
return t->sum;
}
int mid=(l2+r2)>>1ll;
return query2(t->l, l2, mid, y1, min(mid, y2))+query2(t->r, mid+1, r2, max(mid+1, y1), y2 );
}
int query1(n1 *t, int l1, int r1, int l2, int r2, int x1, int x2, int y1, int y2){
if(!t){
return 0;
}
if(x1>x2){
return 0;
}
if( (l1==x1) && (r1==x2) ){
return query2(t->t2, l2, r2, y1, y2);
}
int mid=(l1+r1)>>1ll;
return query1(t->l, l1, mid, l2, r2, x1, min(x2, mid), y1, y2)+query1(t->r, mid+1, r1, l2, r2, max(mid+1, x1), x2, y1, y2);
}
int s[100010], t[100010];
pair<int, pii> pr[100010];
pair<int, pair<int, pii>> qr[100010];
int res[100010];
int32_t main(){
INIT
cin>>n>>q;
for(int i=1; i<=n; i++){
cin>>s[i]>>t[i];
pr[i]={s[i]+t[i], {s[i], t[i]} };
}
sort(pr+1, pr+1+n);
for(int i=1; i<=q; i++){
cin>>qr[i].sc.sc.ft>>qr[i].sc.sc.sc>>qr[i].ft;
qr[i].sc.ft=i;
}
sort(qr+1, qr+1+q);
int ind=n;
for(int i=q; i>=1; i--){
while( (ind>=1) && (pr[ind].ft>=qr[i].ft) ){
update1(t1, 0, 1e9, 0, 1e9, pr[ind].sc.ft, pr[ind].sc.sc);
ind--;
}
res[qr[i].sc.ft ]=query1(t1, 0, 1e9, 0, 1e9, qr[i].sc.sc.ft, 1e9, qr[i].sc.sc.sc, 1e9);
}
for(int i=1; i<=q; i++){
cout<<res[i]<<"\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
144 ms |
85176 KB |
Output is correct |
8 |
Correct |
138 ms |
85176 KB |
Output is correct |
9 |
Correct |
140 ms |
85192 KB |
Output is correct |
10 |
Correct |
95 ms |
59908 KB |
Output is correct |
11 |
Correct |
102 ms |
58196 KB |
Output is correct |
12 |
Correct |
24 ms |
576 KB |
Output is correct |
13 |
Correct |
140 ms |
85256 KB |
Output is correct |
14 |
Correct |
139 ms |
85288 KB |
Output is correct |
15 |
Correct |
139 ms |
85352 KB |
Output is correct |
16 |
Correct |
102 ms |
57292 KB |
Output is correct |
17 |
Correct |
93 ms |
59076 KB |
Output is correct |
18 |
Correct |
21 ms |
528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3125 ms |
661224 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3125 ms |
661224 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
588 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
144 ms |
85176 KB |
Output is correct |
8 |
Correct |
138 ms |
85176 KB |
Output is correct |
9 |
Correct |
140 ms |
85192 KB |
Output is correct |
10 |
Correct |
95 ms |
59908 KB |
Output is correct |
11 |
Correct |
102 ms |
58196 KB |
Output is correct |
12 |
Correct |
24 ms |
576 KB |
Output is correct |
13 |
Correct |
140 ms |
85256 KB |
Output is correct |
14 |
Correct |
139 ms |
85288 KB |
Output is correct |
15 |
Correct |
139 ms |
85352 KB |
Output is correct |
16 |
Correct |
102 ms |
57292 KB |
Output is correct |
17 |
Correct |
93 ms |
59076 KB |
Output is correct |
18 |
Correct |
21 ms |
528 KB |
Output is correct |
19 |
Execution timed out |
3125 ms |
661224 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |