Submission #1218317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218317		Malix	Martian DNA (BOI18_dna)	C++20	100 / 100	119 ms	5116 KiB

dna

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,k,p;
vi a,b,st;

void build(int x,int l,int r){
    if(l==r){
        st[x]=b[l];
        return;
    }
    int m=(l+r)/2;
    build(2*x,l,m);
    build(2*x+1,m+1,r);
    st[x]=max(st[2*x],st[2*x+1]);
}
 
void update(int x,int l,int r,int p,int v){
    if(l==r){
        st[x]+=v;
        return;
    }
    int m=(l+r)/2;
    if(p>m)update(2*x+1,m+1,r,p,v);
    else update(2*x,l,m,p,v);
    st[x]=max(st[2*x],st[2*x+1]);
}

int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// freopen("test_input.txt", "r", stdin);
// freopen("test_output.txt", "w", stdout);
    cin>>n>>k>>p;
    a.resize(n);
    REP(i,0,n)cin>>a[i];
    b.resize(n,0);
    REP(i,0,p){
        int x,y;cin>>x>>y;
        b[x]=y;
    }
    st.resize(4*n+1,0);
    build(1,0,n-1);
    int pos=1,ans=inf;
    update(1,0,n-1,a[0],-1);
    REP(i,0,n){
        while(pos<n&&st[1]>0)update(1,0,n-1,a[pos++],-1);
        if(pos>=n&&st[1]>0)break;
        ans=min(ans,pos-i);
        update(1,0,n-1,a[i],1);
    }
    if(ans==inf)cout<<"impossible";
    else cout<<ans;
}

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