Submission #391944

#TimeUsernameProblemLanguageResultExecution timeMemory
391944Jarif_RahmanIndex (COCI21_index)C++17
110 / 110
1650 ms12288 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define sc second using namespace std; typedef long long int ll; typedef string str; const int sq = 417, lim = 524288; bool mo(tuple<int, int, int> a, tuple<int, int, int> b){ return make_pair(get<0>(a)/sq, get<1>(a)) < make_pair(get<0>(b)/sq, get<1>(b)); } struct segtree{ int k; ll sm[lim]; segtree(int n){ k = lim; } void upd(int in, ll x){ in+=k/2; sm[in] = x, in/=2; while(in > 0){ sm[in] = sm[2*in] + sm[2*in+1]; in/=2; } } inline ll sum(int l, int r, int nd, int a, int b){ if(b < l || a > r) return 0; if(a >= l && b <= r) return sm[nd]; int c = (a+b)/2; return sum(l, r, 2*nd, a, c) + sum(l, r, 2*nd+1, c+1, b); } inline ll sum(int l, int r){ return sum(l, r, 1, 0, k/2-1); } inline ll ans(int a, int b, int nd, ll s){ if(nd >= k/2) return a; int md = (a+b)/2; if(s+sm[2*nd+1] >= md+1) return ans(md+1, b, 2*nd+1, s); return ans(a, md, 2*nd, s+sm[2*nd+1]); } ll get(int in){ return sm[k/2+in]; } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; int v[n]; for(int &x: v) cin >> x; tuple<int, int, int> query[q]; for(int i = 0; i < q; i++){ int l, r; cin >> l >> r; l--, r--; query[i] = {l, r, i}; } vector<int> ans(q); sort(query, query+q, mo); segtree pp(lim); int a = 0, b = 0; pp.upd(v[0], pp.get(v[0])+1); for(auto [l, r, in]: query){ for(int i = a; i < l; i++) pp.upd(v[i], pp.get(v[i])-1); for(int i = a-1; i >= l; i--) pp.upd(v[i], pp.get(v[i])+1); for(int i = b+1; i <= r; i++) pp.upd(v[i], pp.get(v[i])+1); for(int i = b; i > r; i--) pp.upd(v[i], pp.get(v[i])-1); a = l, b = r; ans[in] = pp.ans(0, pp.k/2-1, 1, 0); } for(int x: ans) cout << x << "\n"; }

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:42:25: warning: 'pp.segtree::sm[<unknown>]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |         return sm[k/2+in];
      |                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...