Submission #1112736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112736		0pt1mus23	Martian DNA (BOI18_dna)	C++14	100 / 100	1262 ms	27000 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }
const int mod = 1e9 +7, sze = 2e5 +23, inf = LLONG_MAX, LG = 20;

int T[sze*4];
int mal[sze];
int got[sze];
int gotur=0;
void build(int node,int l,int r){
    if(l==r){
        T[node]=mal[l];
        return;
    }

    int mid = (l+r)/2;
    build(2*node,l,mid);
    build(2*node +1,mid+1,r);
    T[node]=min(T[node *2 ],T[node *2 +1]);
}
int qry(int node,int l,int r,int lx,int rx){
    if( lx>r || rx<l ){
        return inf;
    }
    if(l<=lx && rx<=r){
        return T[node]; 
    }

    int mid = (lx+rx)/2;
    int left = qry(2*node,l,r,lx,mid);
    int right = qry(2*node +1,l,r,mid+1,rx);
    return min(left,right);
}
void upd(int node,int idx,int lx,int rx,int to){
    if(lx==rx){
        T[node]=to;
        return;
    }
    int mid = (lx+rx)/2;
    if( idx<=mid){
        upd(2*node,idx,lx,mid,to);
    }
    else{
        upd(2*node +1,idx,mid+1,rx,to);
    }
    T[node]=min(T[node *2 ],T[node *2 +1]);
}


void fast(){
    int n,k,rq;
    cin>>n>>k>>rq;
    map<int,vector<int>> var;
    
    vector<int> arr(n+1,0);
    generate(arr.begin()+1,arr.end(),nxt);
    
    vector<int> lazim(n+10,0);
    vector<int> last(n+10,0);
    int goturmeli = rq;
    while(rq--){
        int b,q;
        cin>>b>>q;
        lazim[b]=q;
    }
    for(int i=1;i<=n;i++){
        mal[i]=inf;
        if(lazim[arr[i]]){
            mal[i]=-inf;
            if(!var[arr[i]].empty()){
                last[i]=var[arr[i]].back();
            }
            var[arr[i]].pb(i);
            if(var[arr[i]].size()>=lazim[arr[i]]){
                mal[i]=var[arr[i]][ var[arr[i]].size() - lazim[arr[i]] ];
            }
        }
    }
    // for(int i =0;i<n;i++){
    //     cout<<mal[i+1]<<" ";
    // }
    // cout<<endl;
    build(1,0,n);
    // cout<<qry(1,1,2,0,n)<<endl;

    int l =1;
    int r = n;
    int ans=-1;
    // cout<<qry(1,2,5,0,n)<<endl;
    while(l<=r){
        int mid = (l+r)/2;

        bool flag=false;
        gotur = 0;
        for(int i =0;i<=n;i++){
            got[i]=0;
        }
        vector<pair<int,int>> recov;
        for(int i =1;i<=mid;i++){
            if(lazim[arr[i]]){
                if(++got[arr[i]]==1){
                    ++gotur;
                }
                else{
                    recov.pb({last[i],mal[last[i]]});
                    upd(1,last[i],0,n,inf);
                }
            }
        }
        if(gotur == goturmeli && qry(1,1,mid,0,n) > 0){
            flag=true;
        }
        else{

            for(int i =mid+1;i<=n;i++){
                if(lazim[ arr[i - mid] ]){
                    if( (--got[arr[i-mid]]) ==0){
                        --gotur;
                    }
                }
                if(lazim[arr[i]]){
                    if( (++got[arr[i]]) ==1 ){
                        ++gotur;
                    }
                    else{
                        // cout<<mid<<" sil"<<last[i]<<endl;
                        recov.pb({last[i],mal[last[i]]});
                        upd(1,last[i],0,n,inf);
                    }
                }
                if(gotur == goturmeli && qry(1,i-mid+1,i,0,n) > i-mid){
                    // cout<<mid<< " "<<i<<" "<<qry(1,i-mid+1,i,0,n)<<endl;
                    flag=true;
                    break;
                }
            }
        }

        for(auto [p,b]:recov){
            upd(1,p,0,n,b);
        }

        if(flag){
            ans = mid;
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }

    if(ans==-1){
        putr("impossible");
    }
    putr(ans);
}

signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    int tt = 1;

    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

Compilation message (stderr)

dna.cpp: In function 'void fast()':
dna.cpp:80:34: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wsign-compare]
   80 |             if(var[arr[i]].size()>=lazim[arr[i]]){
dna.cpp:145:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  145 |         for(auto [p,b]:recov){
      |                  ^

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32