Submission #1071796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071796		ezzzay	Index (COCI21_index)	C++14	110 / 110	226 ms	14676 KiB

index

#include<iostream>
#include<math.h>
#include<utility>
#include<map>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
#define int long long 
#define ff first
#define ss second
#define pb push_back
const int S = 320;
const int N = 2e5+5;
int arr[N];
map<int,int>cmp;
int cnt=0;
int ans[N];
int val[N];
bool cmp2(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
  if (a.ff.ff / S != b.ff.ff / S) return a.ff.ff< b.ff.ff;
  return (a.ff.ss < b.ff.ss)^(a.ff.ff/S%2);
}
int p=0,k=0;
void add(int a){
    if(a>=p)k++;
    
    val[a]++;
    
    if(k-val[p]>=p+1){
        k-=val[p];
        p++;
    }
}
void rem(int a){
    
    if(a>=p)k--;
    val[a]--;
    
    if(k<p){
        
        p--;
        k+=val[p];
    }
    
    
}
signed main(){
    int n,q;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    int k=1;
    vector<pair<pair<int, int>, int>> qq(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        qq[i] = {{l, r}, i};
    }
    sort(qq.begin(), qq.end(), cmp2);
    int L = 0, R = -1;
    for (int i = 0; i < q; i++) {
        int j = qq[i].ss;
        int l = qq[i].ff.ff;
        int r = qq[i].ff.ss;
       // cout<<l<<" "<<r<<endl; 
        while (R < r) add(arr[++R]);
        while (L > l) add(arr[--L]);
        while (R > r) rem(arr[R--]);
        while (L < l) rem(arr[L++]);
        ans[j]=p;
       
    }
    for(int i=0;i<q;i++){
        cout<<ans[i]<<'\n';
    }
}
/*
8 7
1 2 2 5 6 3 2 1
1 8
2 7
1 4
2 5
2 2
7 8
1 7

3
3
2
2
1
-1
3
*/

Compilation message (stderr)

index.cpp: In function 'int main()':
index.cpp:59:9: warning: unused variable 'k' [-Wunused-variable]
   59 |     int k=1;
      |         ^

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