Submission #1272215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272215		yehudalester	Martian DNA (BOI18_dna)	C++20	100 / 100	417 ms	13316 KiB

dna

#include<bits/stdc++.h>
#include<chrono>
using namespace std;
using namespace chrono;
using ll=long long;
const ll SZ=1<<19;
struct seg{
    vector<ll> vec=vector<ll>(2*SZ,1e18);
    void upd(ll i, ll k){
        vec[i+=SZ]=k;
        while(i/=2)vec[i]=min(vec[2*i],vec[2*i+1]);
    }
    ll get(ll i){
        return vec[i+SZ];
    }
    void add(ll i, ll k){
        upd(i,get(i)+k);
    }
    ll getmin(){
        return vec[1];
    }
};
struct mset{
    seg st;
    mset(vector<ll> r){
        for(ll i=0;i<r.size();i++){
            st.upd(i,-r[i]);
        }
    }
    void add(ll x){
        st.add(x,1);
    }
    void rm(ll x){
        st.add(x,-1);
    }
    bool valid(){
        return st.getmin()>=0;
    }
};
int main(){
    ll n,k,R;cin>>n>>k>>R;
    vector<ll> vec(n);for(ll&i:vec)cin>>i;
    vector<ll> r(k);
    for(ll i=0;i<R;i++){
        ll a,b;cin>>a>>b;
        r[a]=b;
    }{
    mset m(r);
    for(ll i:vec)m.add(i);
    if(!m.valid()){cout<<"impossible";return 0;}
    }
    ll l=0,h=n;
    while(l<h){
        ll m=(l+h)/2;
        mset ms(r);
        for(int i=0;i<m;i++)ms.add(vec[i]);
        for(int i=m;i<n;i++){
            if(ms.valid())break;
            ms.add(vec[i]);ms.rm(vec[i-m]);
        }
        if(ms.valid())h=m;
        else l=m+1;
    }
    cout << h;
    return 0;
}

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