#include <bits/stdc++.h>
using namespace std;
const int MX=4e5+5;
int N,Q;
int S[MX],T[MX], X[MX], Y[MX], Z[MX], ans[MX];
struct fenwick {
int t[MX];
void upd(int pos, int val) {
for(int i=pos;i<MX;i+=i&-i) t[i]+=val;
}
int que(int pos) {
int res=0;
for(int i=pos;i>0;i-=i&-i) res+=t[i];
return res;
}
} ft, tt;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>Q;
for(int i=1;i<=N;i++) cin>>S[i]>>T[i];
for(int i=1;i<=Q;i++) {
cin>>X[i]>>Y[i]>>Z[i];
Z[i]=max(Z[i],X[i]+Y[i]);
}
vector<array<int,4>> v;
for(int i=1;i<=N;i++)
v.push_back({S[i]+T[i],S[i],T[i],MX});
for(int i=1;i<=Q;i++)
v.push_back({Z[i],X[i],Y[i],i});
sort(v.rbegin(),v.rend());
int cnt=0;
for(auto [s,x,y,id]:v) {
if(id==MX) {
cnt+=1;
ft.upd(x,1);
tt.upd(y,1);
} else {
ans[id]=cnt-ft.que(x-1)-tt.que(y-1);
}
}
for(int i=1;i<=Q;i++) {
cout<<ans[i]<<'\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10584 KB |
Output is correct |
2 |
Execution timed out |
3065 ms |
10588 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3052 ms |
19264 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3052 ms |
19264 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10584 KB |
Output is correct |
2 |
Execution timed out |
3065 ms |
10588 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |