Submission #444787

#TimeUsernameProblemLanguageResultExecution timeMemory
444787fcmalkcinExamination (JOI19_examination)C++17
100 / 100
1543 ms87004 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" mt19937_64 rnd; const ll maxn=1e5+10; const ll mod =1e9+7 ; const ll base=3e18; /// you will be the best but now you just are trash /// goal=0/7; struct BIT_2D { vector<ll> vt; vector<vector<ll>> f; vector<vector<ll>> node; void init(vector<ll> vt1) { vt=vt1; sort(vt.begin(),vt.end()); vt.resize(unique(vt.begin(),vt.end())-vt.begin()); f=vector<vector<ll>> (vt.size()+2,vector<ll> (0) ); node=vector<vector<ll>> (vt.size()+2,vector<ll>(0) ); } void rearrange() { for (int i=1; i<=vt.size(); i++) { sort(node[i].begin(),node[i].end()); node[i].resize(unique(node[i].begin(),node[i].end())-node[i].begin()); f[i]=vector<ll> (node[i].size()+2,0); } } void fake_update(ll x,ll y) { for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i<=vt.size(); i+= i&(-i)) { node[i].pb(y); } } void fake_get(ll x,ll y) { for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i; i-= i&(-i)) { node[i].pb(y); } } void update(ll x,ll y,ll val) { for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i<=vt.size(); i+= i&(-i)) { for (int j=lower_bound(node[i].begin(),node[i].end(),y)-node[i].begin()+1; j<=node[i].size(); j+= j&(-j)) { f[i][j]=f[i][j]+val; } } } ll get(ll x,ll y) { ll ans=0; for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i; i-= i&(-i)) { for (int j=lower_bound(node[i].begin(),node[i].end(),y)-node[i].begin()+1; j; j-= j&(-j)) { ans+=f[i][j]; } } return ans; } } man; pll a[maxn]; pair<pll,pll> c[maxn]; bool lf(pll a,pll b) { return a.ff+a.ss<b.ff+b.ss; } bool lf1(pair<pll,pll> a,pair<pll,pll> b) { return a.ss.ff<b.ss.ff; } ll ans[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("t.inp", "r")) { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n, q; cin>> n>> q; vector<ll> vt; for (int i=1; i<=n; i++) { cin>>a[i].ff>>a[i].ss; vt.pb(a[i].ff); } for (int i=1; i<=q; i++) { cin>>c[i].ff.ff>>c[i].ff.ss>>c[i].ss.ff; vt.pb(c[i].ff.ff-1); c[i].ss.ss=i; } vt.pb(base); man.init(vt); for (int i=1; i<=n; i++) { man.fake_update(a[i].ff,a[i].ss); } for (int i=1; i<=q; i++) { man.fake_get(c[i].ff.ff-1,c[i].ff.ss-1); man.fake_get(c[i].ff.ff-1,base); man.fake_get(base,c[i].ff.ss-1); } man.rearrange(); sort(a+1,a+n+1,lf); sort(c+1,c+q+1,lf1); ll j=n; for (int i=q; i>=1; i--) { while (j>=1&&a[j].ff+a[j].ss>=c[i].ss.ff) { man.update(a[j].ff,a[j].ss,1); j--; } ll id=c[i].ss.ss; ans[id]=(n-j+man.get(c[i].ff.ff-1,c[i].ff.ss-1)-man.get(c[i].ff.ff-1,base)-man.get(base,c[i].ff.ss-1)); } /* for (int t=1; t<=j; t++) man.update(a[t].ff,a[t].ss,1); for (int i=q; i>=1; i--) { ll id=c[i].ss.ss; ans[id]+=(n+man.get(c[i].ff.ff-1,c[i].ff.ss-1)-man.get(c[i].ff.ff-1,base)-man.get(base,c[i].ff.ss-1)); }*/ for (int i=1; i<=q; i++) cout <<ans[i]<<endl; }

Compilation message (stderr)

examination.cpp: In member function 'void BIT_2D::rearrange()':
examination.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int i=1; i<=vt.size(); i++)
      |                       ~^~~~~~~~~~~
examination.cpp: In member function 'void BIT_2D::fake_update(long long int, long long int)':
examination.cpp:42:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i<=vt.size(); i+= i&(-i))
      |                                                                     ~^~~~~~~~~~~
examination.cpp: In member function 'void BIT_2D::update(long long int, long long int, long long int)':
examination.cpp:56:70: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i=lower_bound(vt.begin(),vt.end(),x)-vt.begin()+1; i<=vt.size(); i+= i&(-i))
      |                                                                     ~^~~~~~~~~~~
examination.cpp:58:89: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int j=lower_bound(node[i].begin(),node[i].end(),y)-node[i].begin()+1; j<=node[i].size(); j+= j&(-j))
      |                                                                                        ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...