Submission #1150200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150200		Robert_junior	Martian DNA (BOI18_dna)	C++20	100 / 100	76 ms	5960 KiB

dna

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define F first
#define S second
const int N = 3e5 + 7, M = 5e5 + 7;
int t[N * 4];
int a[N];
void upd(int v, int l, int r, int idx, int val){
    if(l == r){
        t[v] += val;
    }
    else{
        int m = (l + r) / 2;
        if(idx <= m) upd(v + v, l, m, idx, val);
        else upd(v + v + 1, m + 1, r, idx, val);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
}
void solve(){
    int n, m, k;
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        a[i]++;
    }
    int i = 1, j = 1;
    for(int i = 1; i <= k; i++){
        int x, y;
        cin>>x>>y;
        x++;
        upd(1, 1, m, x, -y);
    }
    int ans = INT_MAX;
    while(i <= n){
        while(i <= n && t[1] < 0){
            upd(1, 1, m, a[i], 1);
            i++;
        }
        while(j <= n && t[1] >= 0){
            ans = min(ans, i - j);
            upd(1, 1, m, a[j], -1);
            j++;
        }
    }
    if(ans == INT_MAX) cout<<"impossible";
    else cout<<ans;
}
main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin>>t; 
    for(int i = 1; i <= t; i++){
        //cout<<"Case "<<i<<": ";
        solve();
    }
}

Compilation message (stderr)

dna.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main(){
      | ^~~~

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