Submission #1110798

#TimeUsernameProblemLanguageResultExecution timeMemory
1110798vjudge1Examination (JOI19_examination)C++17
0 / 100
3082 ms10408 KiB
#include <bits/stdc++.h> using namespace std; typedef int 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() #define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 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(){ FIN; 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(100000+5); BIT mat(100000+5); 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...