Submission #792637

#	Time	Username	Problem	Language	Result	Execution time	Memory
792637		huutuan	Index (COCI21_index)	C++14	110 / 110	593 ms	62828 KiB

index

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

struct FenwickTree{
   int n; vector<int> t;

   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }

   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
   }

   void init(int _n, int* a){
      init(_n);
      for (int i=1; i<=n; ++i) update(i, a[i]);
   }

   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans+=t[i];
      return ans;
   }

   int get(int l, int r){
      return get(r)-get(l-1);
   }
} bit;

const int N=2e5+1;
int n, q;
int l[N], r[N], a[N];
pair<int, int> qq[N];
vector<int> v[N], pos[N];

void solve(int tc){
   // cout << "Case #" << tc << ": ";
   cin >> n >> q;
   vector<int> vals;
   for (int i=1; i<=n; ++i) cin >> a[i], pos[a[i]].push_back(i);
   for (int i=1; i<=q; ++i){
      cin >> qq[i].first >> qq[i].second;
      l[i]=1, r[i]=2e5;
   }
   for (int rep=1; rep<=20; ++rep){
      for (int i=1; i<=q; ++i) if (l[i]<=r[i]) v[(l[i]+r[i])>>1].push_back(i);
      bit.init(n);
      for (int i=2e5; i>=1; --i){
         for (int j:pos[i]) bit.update(j, 1);
         for (int j:v[i]){
            if (bit.get(qq[j].first, qq[j].second)>=i) l[j]=i+1;
            else r[j]=i-1;
         }
         v[i].clear();
      }
   }
   for (int i=1; i<=q; ++i) cout << r[i] << '\n';
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve(i);
   return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50