Submission #493825

#TimeUsernameProblemLanguageResultExecution timeMemory
493825mars4Examination (JOI19_examination)C++17
100 / 100
1149 ms110072 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ff first #define ss second #define ll int64_t #define ld long double #define nl cout<<"\n" #define all(v) v.begin(),v.end() #define mset(a,v) memset((a),(v),sizeof(a)) #define forn(i,a,b) for(int64_t i=int64_t(a);i<int64_t(b);++i) #define forb(i,a,b) for(int64_t i=int64_t(a);i>=int64_t(b);--i) #define fastio() ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define mod 1'000'000'007 #define mod2 998'244'353 #define inf 1'000'000'000'000'007 #define pi 3.14159265358979323846 template<class key,class cmp=std::less<key>> using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>; template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p) {return out<<"("<<p.ff<<", "<<p.ss<<")";} template<class T> ostream& operator<<(ostream& out,vector<T> &v) {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";} template<class T> ostream& operator<<(ostream& out,deque<T> &v) {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";} template<class T> ostream& operator<<(ostream& out,set<T> &s) {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";} template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m) {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";} void dbg_out() {cerr<<"]\n";} template<typename Head,typename... Tail> void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);} #ifdef LOCAL #define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__) #else #define dbg(...) #endif //---------------------------------mars4--------------------------------- template<class T> class MergeSortTree { ll N; ll lesser_than(ll i,ll val) { ll res=0; for(;i;i-=i&(-i)) { res+=fentree[i].order_of_key(val); } return res; } ll greater_than(ll i,ll val) { ll res=0; for(;i;i-=i&(-i)) { res+=(ll)fentree[i].size()-fentree[i].order_of_key(val+1); } return res; } public: vector<ordered_set<T,less_equal<T>>> fentree; void init(ll n) { N=n; fentree=vector<ordered_set<T,less_equal<T>>>(N+1); } void build(vector<ll> &a) { for(ll i=1;i<=N;i++) { fentree[i].insert(a[i-1]); if(i+(i&-i)<=N) { for(ll j:fentree[i]) { fentree[i+(i&-i)].insert(j); } } } } void update(ll i,ll val) { for(i++;i<=N;i+=i&(-i)) { fentree[i].insert(val); } } ll lesser_than(ll l,ll r,ll val) { return lesser_than(r+1,val)-lesser_than(l,val); } ll greater_than(ll l,ll r,ll val) { return greater_than(r+1,val)-greater_than(l,val); } ll count(ll l,ll r,ll val) { ll len=r-l+1; ll gt=greater_than(l,r,val); ll lt=lesser_than(l,r,val); return len-gt-lt; } }; struct st { ll a,b,c,id; bool operator < (const st &o) const { return a<o.a; } }; int main() { fastio(); ll z,n,m,t,k,i,j,l,d,h,r; cin>>n>>m; vector<st> marks(n); vector<st> queries(m); vector<ll> comp; forn(i,0,n) { auto &[a,b,c,id]=marks[i]; cin>>a>>b; comp.push_back(b); c=a+b; id=i; } forn(i,0,m) { auto &[a,b,c,id]=queries[i]; cin>>a>>b>>c; comp.push_back(b); id=i; } sort(all(comp)); for(auto &[a,b,c,id]:marks) { b=lower_bound(all(comp),b)-comp.begin(); } for(auto &[a,b,c,id]:queries) { b=lower_bound(all(comp),b)-comp.begin(); } sort(all(marks)); sort(all(queries)); MergeSortTree<int> mt; mt.init(n+m); vector<ll> ans(m); j=m-1; forb(i,n-1,0) { auto [a,b,c,id]=marks[i]; while(j>=0 and queries[j].a>a) { ans[queries[j].id]=mt.greater_than(queries[j].b,n+m-1,queries[j].c-1); j--; } mt.update(b,c); } while(j>=0) { ans[queries[j].id]=mt.greater_than(queries[j].b,n+m-1,queries[j].c-1); j--; } for(ll i:ans) { cout<<i<<"\n"; } cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n"; return 0; }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:131:5: warning: unused variable 'z' [-Wunused-variable]
  131 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |     ^
examination.cpp:131:11: warning: unused variable 't' [-Wunused-variable]
  131 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |           ^
examination.cpp:131:13: warning: unused variable 'k' [-Wunused-variable]
  131 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |             ^
examination.cpp:131:15: warning: unused variable 'i' [-Wunused-variable]
  131 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |               ^
examination.cpp:131:19: warning: unused variable 'l' [-Wunused-variable]
  131 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                   ^
examination.cpp:131:21: warning: unused variable 'd' [-Wunused-variable]
  131 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                     ^
examination.cpp:131:23: warning: unused variable 'h' [-Wunused-variable]
  131 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                       ^
examination.cpp:131:25: warning: unused variable 'r' [-Wunused-variable]
  131 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...