Submission #476487

#TimeUsernameProblemLanguageResultExecution timeMemory
476487nekiIndex (COCI21_index)C++14
60 / 110
2583 ms99476 KiB
#include <bits/stdc++.h> #define ll int #define loop(i, a, b) for(ll i=a;i<b;++i) #define pool(i, a, b) for(ll i=a-1;i>=b;--i) #define fore(i, a) for(auto&& i:a) #define fi first #define se second #define ps(a) push_back(a) #define pb(a) pop_back(a) #define eb(...) emplace_back(__VA_ARGS__) #define sc scanf #define vc vector #define lb lower_bound #define ub upper_bound #define all(a) a.begin(), a.end() #define llmax LLONG_MAX/2 #define llmin -LLONG_MAX/2 using namespace std; #define mn 500100 #define par pair<ll, ll> #define ld long double #define mod 1000000007 int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll n, q;cin >> n >> q; vc<vc<ll>> tr(2 * n); loop(i, 0, n) {ll t;cin >> t;tr[i+n].eb(t);} pool(i, n, 1) tr[i].resize(tr[i * 2].size() + tr[i * 2 + 1].size()); pool(no, n, 1) merge(all(tr[no * 2]), all(tr[no * 2 +1]), tr[no].begin()); vc<vc<ll>> prno(q); loop(i, 0, q){ ll ql, qr;cin >> ql >> qr;--ql; for(ql+=n, qr+=n;ql<qr;ql>>=1, qr>>=1){ if(ql&1) prno[i].ps(ql++); if(qr&1) prno[i].ps(--qr); } } vc<ll> l(q, 1), r(q, n), mid(q); while(1){ vc<ll> act; loop(i, 0, q) if(l[i]<r[i]) act.ps(i), mid[i]=(l[i]+r[i]+1)/2; if(act.size()==0) break; //sort(all(act), [&](ll a, ll b){return mid[a]<mid[b];}); vc<vc<ll>> ques(2 * n); vc<ll> sum(q, 0); fore(i, act){ fore(v, prno[i]) ques[v].eb(i); } loop(i, 1, 2 * n) fore(v, ques[i]){ sum[v]+=tr[i].end()-lower_bound(all(tr[i]), mid[v]); } fore(i, act){ if(mid[i]<=sum[i]) l[i]=mid[i]; else r[i]=mid[i]-1; } } loop(i, 0, q) cout << l[i] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...