제출 #1311516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311516		waelkb	Martian DNA (BOI18_dna)	C++20	0 / 100	171 ms	6612 KiB

dna

#include <bits/stdc++.h>

using namespace std;

#define mid (l + ((r - l) / 2))
#define pb push_back
#define F first
#define S second

int64_t mod = 998244353 ;

void solve(int64_t tt)
{
    int64_t n, m, k, x = -1, y = 0, z = 1, ans = 1e18, sum = 0, p = 1, cnt = 0, cnt0 = 0, cnt1 = 0, mx = -1, mn = 1e18 ;
    string s, t = "" ;
    bool ok = 1 ;
    cin >> n >> m >> k ;
    vector<int64_t> a(n + 1), b(k + 1), c(k + 1) ;
    for(int64_t i = 1 ; i <= n ; i++) cin >> a[i] ;
    /*c[0]++,*/ cnt = k ;
    for(int64_t i = 1 ; i <= k ; i++)
    {
        cin >> x >> y ;
        b[x] = y ;
    }

    for(int64_t i = 0 ; i <= n ; i++)
    {
        if(i > 0) c[a[i]]-- ;
        if(i && c[a[i]] == b[a[i]] - 1) cnt++ ;
        while(p <= n && cnt > 0)
        {
            if(c[a[p]] + 1 == b[a[p]]) cnt-- ;
            c[a[p]]++, p++ ;
        }
        cout << i << ' ' << p << ' ' << cnt << endl;
        if(!cnt) ans = min(ans , p - i + 1) ;
    }
    if(ans == 1e18) cout << "impossible" << endl;
    else cout << ans - 2 << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    /*freopen("defining_prizes_validation_input.txt", "r", stdin);
    freopen("BVout.txt", "w", stdout);*/
    int tt = 1 ;
    //cin >> tt ;
    for(int64_t i = 1 ; i <= tt ; i++) solve(i) ;
}

/*
 *      empty space to be able to see the last part of the code ;)
 *
 *      some advices :
 *      https://codeforces.com/blog/entry/146051
 *      https://codeforces.com/blog/entry/22616
 *      do not eat penaltieeeeeeeeeeeeeeeeeeeeeeeeeeeees in official contests you are the last of people who solved like you, you are so ugly
 *      do not forget to zero your global arrays in test cases
 *      check the limits of your code
 *      test edge cases (the least n , the biggest n if you can , etc...)
 *      run time error may happened because of exceed the limits (but it may happen when you devide or "'mod'" by zero)
 *      writing....
 *      ...
 *      ..
 *      .
 */

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