Submission #707069

#TimeUsernameProblemLanguageResultExecution timeMemory
707069AntekbExamination (JOI19_examination)C++14
100 / 100
457 ms33960 KiB
#include<bits/stdc++.h> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("trapv") #define st first #define nd second #define pb push_back #define eb emplace_back #define pp(x) pop_back(x) #define mp(a, b) make_pair(a, b) #define all(x) (x).begin(), (x).end() #define rev(x) reverse(all(x)) #define sor(x) sort(all(x)) #define sz(x) (int)(x).size() #define rsz(x) resize(x) using namespace std; ///~~~~~~~~~~~~~~~~~~~~~~~~~~ template <typename H, typename T> ostream& operator<<(ostream& os, pair<H, T> m){ return os <<"("<< m.st<<", "<<m.nd<<")"; } template <typename H> ostream& operator<<(ostream& os, vector<H> V){ os<<"{"; for(int i=0; i<V.size(); i++){ if(i)os<<" "; os<<V[i]; } os<<"}"; return os; } void debug(){cerr<<"\n";} template <typename H, typename... T> void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);} #define deb(x...) cerr<<#x<<" = ";debug(x); //#define deb(x...) ; ///~~~~~~~~~~~~~~~~~~~~~~~~~ typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii > vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef string str; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int K=17, N=1<<K, INF=1e9+5, mod2=1e9+7, mod=998244353; struct modint{ int n=0; modint(){} modint(ll x){ n=x%mod; if(n<0)n+=mod; } operator int(){ return n; } modint operator+(modint a){a.n = n+a.n; if(a.n>=mod)a.n-=mod;return a;} modint operator+=(modint a){return (*this)=(*this)+a;} modint operator-(modint a){a.n = n-a.n; if(a.n<0)a.n+=mod;return a;} modint operator-=(modint a){return (*this)=(*this)-a;} modint operator*(modint a){a.n = (n*1ll*a.n)%mod; return a;} modint operator*=(modint a){return (*this)=(*this)*a;} modint operator^(const ll &m)const{ modint a(1); if(m==0)return a; if(m==1)return (*this); a=(*this)^(m/2); a*=a; return a*((*this)^(m&1)); } modint odw(){ return (*this)^((ll)mod-2); } modint operator/(modint a){return (*this)*a.odw();} modint operator/=(modint a){return (*this)=(*this)/a;} bool operator==(modint a){return a.n==n;} friend ostream& operator<<(ostream& os, modint m) { return os << m.n; } }; modint fact[N], fact2[N]; typedef vector<modint> vm; void factinit(){ fact[0]=1; for(int i=1; i<N; i++){ fact[i]=(fact[i-1]*modint(i))%mod; } fact2[N-1]=fact[N-1].odw(); for(int i=N-2; i>=0; i--){ fact2[i]=(fact2[i+1]*modint(i+1))%mod; } } modint npok(int _n, int _k){ return fact[_n]*fact2[_k]*fact2[_n-_k]; } int A[N], B[N], tab[N+N], ans[N], L[N+N], R[N+N]; vector<pair<int, int> > quer[N+N]; void add(int v, int c){ //deb(v, c); for(v+=N; v; v>>=1){ tab[v]+=c; //deb(v); } } int sum(int l){ //deb(l, tab[1]); if(l==0)return tab[1]; int res=0; for(l+=N; l>1; l>>=1){ if(l&1){ //deb(l); res+=tab[l++]; } } //deb(res); return res; } int main(){ //factinit(); BOOST; int n, q; cin>>n>>q; vector<pair<int, pii>> V(n); map<int, int> M; M[INF]=1; for(int i=0; i<N; i++){ L[i+N]=R[i+N]=i; } for(int i=N-1; i; i--){ L[i]=L[i+i]; R[i]=R[i+i+1]; } for(auto &i:V)cin>>i.nd.st>>i.nd.nd, i.st=i.nd.st+i.nd.nd, M[i.nd.nd]=1; int wsk=1; for(auto &i:M){ i.nd=wsk++; } for(auto &i:V){ i.nd.nd=M[i.nd.nd]; } sort(V.begin(), V.end()); //deb(V); for(int qq=0;qq<q;qq++){ int s; cin>>A[qq]>>B[qq]>>s; B[qq]=M.lower_bound(B[qq])->nd; int k=lower_bound(all(V), mp(s, mp(0, 0)))-V.begin()+N-1; if(k==N-1)quer[1].pb(mp(A[qq], qq)); else{ while(k>0){ if(!(k&1)){ //if(L[k+1]<n){ deb(k+1, qq, A[qq], B[qq]);} quer[k+1].pb(mp(A[qq], qq)); } k/=2; } } } for(int i=1; i<N+N; i++){ if(!quer[i].size() || L[i]>=n)continue; //deb(i, L[i], R[i]); sor(quer[i]); vii V2; for(int j=L[i]; j<=R[i] && j<V.size(); j++){ V2.pb(V[j].nd); } sor(V2); for(int j=V2.size(); j>=0; j--){ if(j!=V2.size())add(V2[j].nd, 1); while(quer[i].size() && (j==0 || quer[i].back().st>V2[j-1].st)){ ans[quer[i].back().nd]+=sum(B[quer[i].back().nd]); quer[i].pp(); } } for(int j=V2.size()-1; j>=0; j--){ add(V2[j].nd,-1); } } for(int i=0; i<q; i++){ cout<<ans[i]<<"\n"; } }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:186:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |   for(int j=L[i]; j<=R[i] && j<V.size(); j++){
      |                              ~^~~~~~~~~
examination.cpp:191:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |    if(j!=V2.size())add(V2[j].nd, 1);
      |       ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...