Cod sursa(job #2743329)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 22 aprilie 2021 20:19:40
Problema Pq Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 2.81 kb
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream in("pq.in");
ofstream out("pq.out");

int v[nmax],ap[nmax],ma,sol[nmax],idx[nmax],nxt[nmax],prv[nmax];

const int bucket_size = 300;

set <int, greater<int> > s;

pair<int,int> itv[nmax];

bool comp(int st, int dr){
    int st_buk = itv[st].first/bucket_size;
    int dr_buk = itv[dr].first/bucket_size;
    if(st_buk == dr_buk){
        if(st_buk%2){
            return itv[st].second > itv[dr].second;
        }
        else{
            return itv[st].second < itv[dr].second;
        }
    }
    return st_buk < dr_buk;
}

int main(){
    int n,q;
    in >> n >> q;
    for(int i=1; i<=n; i++){
        in >> v[i];
        if(ap[v[i]]){
            nxt[ap[v[i]]] = i;
            prv[i] = ap[v[i]];
        }
        ap[v[i]] = i;
    }
    for(int i=0; i<q; i++){
        in >> itv[i].first >> itv[i].second;
        idx[i] = i;
    }
    sort(idx, idx+q, comp);
    memset(ap, 0, sizeof(ap));
    int cura = itv[idx[0]].first, curb = itv[idx[0]].second;
    for(int a=itv[idx[0]].first; a<=itv[idx[0]].second; a++){
        if(prv[a] >= cura){
            int length = a - prv[a];
            if(ap[length] == 0){
                s.insert(length);
            }
            ap[length]++;
        }
    }
    if(s.size() == 0){
        sol[idx[0]] = -1;
    }
    else
        sol[idx[0]] = *(s.begin());
    for(int i=1; i<q; i++){
        int a = itv[idx[i]].first;
        int b = itv[idx[i]].second;
        while(curb < b){
            curb++;
            if(prv[curb] >= a && prv[curb]){
                int length = curb - prv[curb];
                if(ap[length] == 0){
                    s.insert(length);
                }
                ap[length]++;
            }
        }
        while(cura > a){
            cura--;
            if(nxt[cura] <= b && nxt[cura]){
                int length = nxt[cura] - cura;
                if(ap[length] == 0){
                    s.insert(length);
                }
                ap[length]++;
            }
        } 
        while(curb > b){
            if(prv[curb] >= cura && prv[curb]){
                int length = curb - prv[curb];
                assert(ap[length] > 0);
                ap[length]--;
                if(ap[length] == 0)
                    s.erase(length);
            }
            curb--;
        }
        while(cura < a){
            if(nxt[cura] <= curb && nxt[cura]){
                int length = nxt[cura] - cura;
                assert(ap[length] > 0);
                ap[length]--;
                if(ap[length] == 0)
                    s.erase(length);
            }
            cura++;
        }
        if(s.size() == 0){
            sol[idx[i]] = -1;
        }
        else
            sol[idx[i]] = *(s.begin());
    }
    for(int i=0; i<q; i++){
        out << sol[i] << '\n';
    }
    return 0;
}