#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e5 + 9;
const ll inf = 1e9 + 7;
vector<ll> v,node[N],bit[N];
struct student{
ll A,B,AB;
};
student a[N];
bool lf (student a,student b){
return a.AB < b.AB;
}
struct Query{
ll X,Y,Z,id;
};
Query q[N];
bool lf2(Query a,Query b){
return a.Z < b.Z;
}
ll n,Q,ans[N];
ll Search(ll x){
return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}
void compress(){
sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin());
for (ll i = 1;i <= n;i++) a[i].A = Search(a[i].A),a[i].B = Search(a[i].B);
for (ll i = 1;i <= Q;i++) q[i].X = Search(q[i].X),q[i].Y = Search(q[i].Y);
}
void fakeupd(ll x,ll y){
for (ll i = x;i < N;i += i & -i) node[i].push_back(y);
}
void fakeget(ll x,ll y){
for (ll i = x;i > 0;i -= i & -i) node[i].push_back(y);
}
ll Find(ll id,ll x){
return lower_bound(node[id].begin(),node[id].end(),x) - node[id].begin() + 1;
}
ll upd(ll x,ll y){
for (ll i = x;i < N;i += i & -i)
for (ll j = Find(i,y);j <= node[i].size();j += j & -j) bit[i][j]++;
}
ll Get(ll x,ll y){
ll res = 0;
for (ll i = x;i > 0;i -= i & -i)
for (ll j = Find(i,y);j > 0;j -= j & -j) res += bit[i][j];
return res;
}
ll cal(ll x,ll y){
return Get(N - 1,N - 1) - Get(N - 1,y - 1) - Get(x - 1,N - 1) + Get(x - 1,y - 1);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n>>Q;
for (ll i = 1;i <= n;i++){
cin>>a[i].A>>a[i].B; v.push_back(a[i].A); v.push_back(a[i].B);
a[i].AB = a[i].A + a[i].B;
}
sort(a + 1,a + n + 1,lf);
for (ll i = 1;i <= Q;i++){
cin>>q[i].X>>q[i].Y>>q[i].Z,q[i].id = i;
v.push_back(q[i].X); v.push_back(q[i].Y);
}
sort(q + 1,q + Q + 1,lf2); compress();
//for (ll i = 1;i <= 1;i++) cout<<q[i].X<<" "<<q[i].Y<<" "<<q[i].Z<<"\n"; return 0;
for (ll i = 1;i <= n;i++) fakeupd(a[i].A,a[i].B); fakeget(N - 1,N - 1);
for (ll i = 1;i <= Q;i++){
fakeget(q[i].X - 1,q[i].Y - 1); fakeget(q[i].X - 1,N - 1);
fakeget(N - 1,q[i].Y - 1);
}
for (ll i = 1;i < N;i++){
node[i].push_back(inf); sort(node[i].begin(),node[i].end());
node[i].resize(unique(node[i].begin(),node[i].end()) - node[i].begin());
bit[i].resize(node[i].size() + 3);
}
ll cur = n;
for (ll i = Q;i >= 1;i--){
while(cur && a[cur].AB >= q[i].Z) upd(a[cur].A,a[cur].B),cur--;
ans[q[i].id] = cal(q[i].X,q[i].Y);
}
for (ll i = 1;i <= Q;i++) cout<<ans[i]<<"\n";
}
Compilation message
examination.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
1 | #pragma GCC optimization "Ofast"
|
examination.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
examination.cpp: In function 'int upd(int, int)':
examination.cpp:55:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (ll j = Find(i,y);j <= node[i].size();j += j & -j) bit[i][j]++;
| ~~^~~~~~~~~~~~~~~~~
examination.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
56 | }
| ^
examination.cpp: In function 'int main()':
examination.cpp:88:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
88 | for (ll i = 1;i <= n;i++) fakeupd(a[i].A,a[i].B); fakeget(N - 1,N - 1);
| ^~~
examination.cpp:88:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
88 | for (ll i = 1;i <= n;i++) fakeupd(a[i].A,a[i].B); fakeget(N - 1,N - 1);
| ^~~~~~~
examination.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
73 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
134 ms |
111476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
555 ms |
170424 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
555 ms |
170424 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
134 ms |
111476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
