Submission #1244339

#TimeUsernameProblemLanguageResultExecution timeMemory
1244339minhpkIndex (COCI21_index)C++20
110 / 110
683 ms100044 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a,b; int z[1000005]; vector <int> pos[1000005]; pair<int,int> q[1000005]; vector <int> v[1000005]; int res[1000005]; int l[1000005]; int r[1000005]; int bit[1000005]; vector <int> used; void update(int i,int val){ i++; while (i<=a+64){ if (bit[i]==0){ used.push_back(i); } bit[i]+=val; i+=i&-i; } } int query(int i){ i++; int res=0; while (i>0){ res+=bit[i]; i-=i&-i; } return res; } void reset(){ for (auto p:used){ bit[p]=0; } used.clear(); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> a >> b; int max1=0; for (int i=1;i<=a;i++){ cin >> z[i]; pos[z[i]].push_back(i); max1=max(max1,z[i]); } for (int i=1;i<=b;i++){ cin >> q[i].first >> q[i].second; l[i]=1; r[i]=max1; } // cout << "\n"; while (true){ bool check=true; for (int i=1;i<=b;i++){ if (l[i]<=r[i]){ check=false; int mid=(l[i]+r[i])/2; v[mid].push_back(i); } } if (check){ break; } reset(); for (int i=max1;i>=1;i--){ for (auto p:pos[i]){ update(p,1); } for (auto p:v[i]){ int sl=query(q[p].second)-query(q[p].first-1); // cout << sl << " " << q[p].first << " " << q[p].second << "\n"; if (sl>=i){ res[p]=i; l[p]=i+1; }else{ r[p]=i-1; } } v[i].clear(); } } for (int i=1;i<=b;i++){ cout << res[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...