제출 #750535

#제출 시각아이디문제언어결과실행 시간메모리
750535mars4Examination (JOI19_examination)C++17
100 / 100
1327 ms125580 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 i128 __int128_t #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 T> ostream& operator<<(ostream& out,ordered_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 nval) { for(i++;i<=N;i+=i&(-i)) { fentree[i].insert(nval); } } 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) { if(l>r) { return 0; } 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; } }; int main() { fastio(); ll z,n,m,t,k,i,j,l,d,h,r; cin>>n>>m; vector<array<ll,3>> a(n); vector<array<ll,4>> q(n); vector<ll> vl; vector<ll> vr; for(auto &[l,r,tot]:a) { cin>>l>>r; tot=l+r; vl.push_back(l); vr.push_back(r); } sort(all(vl)); sort(all(vr)); for(auto &[l,r,tot]:a) { l=lower_bound(all(vl),l)-vl.begin(); r=lower_bound(all(vr),r)-vr.begin(); } forn(i,0,m) { auto &[l,r,tot,ind]=q[i]; cin>>l>>r>>tot; l=lower_bound(all(vl),l)-vl.begin(); r=lower_bound(all(vr),r)-vr.begin(); ind=i; } sort(all(a),greater<array<ll,3>>()); sort(all(q),greater<array<ll,4>>()); MergeSortTree<ll> mt; mt.init(n); j=0; vector<ll> ans(m); forn(i,0,m) { while(j<n and a[j][0]>=q[i][0]) { mt.update(a[j][1],a[j][2]); j++; } ans[q[i][3]]=mt.greater_than(q[i][1],n-1,q[i][2]-1); } for(ll i:ans) { cout<<i<<"\n"; } cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int main()':
examination.cpp:128:5: warning: unused variable 'z' [-Wunused-variable]
  128 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |     ^
examination.cpp:128:11: warning: unused variable 't' [-Wunused-variable]
  128 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |           ^
examination.cpp:128:13: warning: unused variable 'k' [-Wunused-variable]
  128 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |             ^
examination.cpp:128:15: warning: unused variable 'i' [-Wunused-variable]
  128 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |               ^
examination.cpp:128:19: warning: unused variable 'l' [-Wunused-variable]
  128 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                   ^
examination.cpp:128:21: warning: unused variable 'd' [-Wunused-variable]
  128 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                     ^
examination.cpp:128:23: warning: unused variable 'h' [-Wunused-variable]
  128 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                       ^
examination.cpp:128:25: warning: unused variable 'r' [-Wunused-variable]
  128 |  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...