#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,a,b) for(int i = a ; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int) x.size()
struct Student{
ll M,I;
};
bool operator <(const Student &a, const Student &b){
if(a.M<b.M) return true;
if(a.M>b.M) return false;
return (a.I<b.I);
}
struct BIT{
ll n;
vector<ll> ft;
BIT(ll n):n(n),ft(n+5,0){}
void upd(ll x,ll y){
while(x<=n){
ft[x]+=y;
x+=(x&-x);
}
}
ll query(ll x){
ll res = 0;
while(x>=1){
res+=ft[x];
x-=(x&-x);
}
return res;
}
};
int main(){
ll n,q; cin>>n>>q;
vector<pair<ll,Student>> student(n); for(auto &i:student) cin>>i.snd.M>>i.snd.I, i.fst=(i.snd.M+i.snd.I);
vector<Student> studentS(n); forn(i,0,n) studentS[i]=student[i].snd;
sort(ALL(student));
vector< pair<pair<ll,ll>,pair<ll,ll> >> query(q);
vector< pair<pair<ll,ll>,pair<ll,ll> >> queryS(q);
sort(ALL(studentS));
ll aux = 0;
for(auto &i:query) cin>>i.snd.fst>>i.snd.snd>>i.fst.fst, i.fst.fst*=-1,i.fst.snd=aux, aux++;
sort(ALL(query));
//ll ind;
//for(auto &i:query) ind = i.fst.snd, queryS[ind].fst.fst=i.snd.fst*-1, queryS[ind].fst.snd=i.snd.snd, queryS[ind].snd.fst = i.fst.fst , queryS[ind].snd.snd = i.fst.snd;
forn(i,0,q){
queryS[i].fst.fst=query[i].snd.fst*-1;
queryS[i].fst.snd=query[i].snd.snd;
queryS[i].snd.fst=query[i].fst.fst*-1;
queryS[i].snd.snd=query[i].fst.snd;
}
sort(ALL(queryS));
BIT inf(1000000);
BIT mat(1000000);
vector<ll> res(q);
for(auto i:query){
if(i.fst.fst*-1<i.snd.fst+i.snd.snd) continue;
while(!student.empty()&&student[SZ(student)-1].fst>=i.fst.fst*-1){
mat.upd(student[SZ(student)-1].snd.M,1);
inf.upd(student[SZ(student)-1].snd.I,1);
/*cout<<"Se agrego a "<<student[SZ(student)-1].snd.M<<" en matematica\n";
cout<<"Se agrego a "<<student[SZ(student)-1].snd.I<<" en informatica\n";
cout<<"Verificando matematica: "<<mat.query(student[SZ(student)-1].snd.M)-mat.query(student[SZ(student)-1].snd.M-1)<<'\n';
cout<<"Verificando matematica: "<<inf.query(student[SZ(student)-1].snd.I)-inf.query(student[SZ(student)-1].snd.I-1)<<'\n';*/
student.pop_back();
}
ll mate = mat.query(1000000)-mat.query(i.snd.fst-1);
ll info = inf.query(1000000)-inf.query(i.snd.snd-1);
//cout<<mate<<" "<<info<<" "<<(n-SZ(student))<<'\n';
res[i.fst.snd]=mate+info-(n-SZ(student));
}
BIT lbit(1000000);
for(auto i:queryS){
//cout<<i.snd.fst<<" "<<i.fst.fst*-1<<"+"<<i.fst.snd<<'\n';
if(i.snd.fst>=i.fst.fst*-1+i.fst.snd) continue;
/*cout<<"entro en la query "<<i.snd.snd<<'\n';
cout<<studentS[SZ(studentS)-1].M<<'\n';*/
while(!studentS.empty()&&studentS[SZ(studentS)-1].M>=i.fst.fst*-1){
lbit.upd(studentS[SZ(studentS)-1].I,1);
//cout<<"Se agrego "<<studentS[SZ(studentS)-1].I<<" a informatica.\n";
studentS.pop_back();
}
//cout<<lbit.query(1000000)<<'\n';
res[i.snd.snd]=lbit.query(1000000)-lbit.query(i.fst.snd-1);
}
for(auto i:res) cout<<i<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
23888 KB |
Output is correct |
| 2 |
Correct |
6 ms |
23888 KB |
Output is correct |
| 3 |
Correct |
6 ms |
23788 KB |
Output is correct |
| 4 |
Runtime error |
24 ms |
32080 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3054 ms |
37192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3054 ms |
37192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
23888 KB |
Output is correct |
| 2 |
Correct |
6 ms |
23888 KB |
Output is correct |
| 3 |
Correct |
6 ms |
23788 KB |
Output is correct |
| 4 |
Runtime error |
24 ms |
32080 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
