oj.uz

답안 #653681

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653681 2022-10-27T16:57:36 Z veiga Martian DNA (BOI18_dna) C++17
100 / 100
 37 ms 7116 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
#define endl "\n"
const int INF = 1e9+10;
const int MOD = 1e9+7;

int n, k, t;
int v[200020];
int need[200020]; 

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> t;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for(int i = 0; i < t; i++) {
        int a, b; cin >> a >> b;
        need[a] = b; 
    }
    int l = 0, r = 0, ok = 0;
    int cnt[200020] = {};
    bool okay[200020] = {};
    cnt[v[r]]++;
    int resp = INF;
    if(need[v[r]] != 0 and cnt[v[r]] >= need[v[r]]) {
        ok++;
        okay[v[r]] = true;
    } 
    while(r < n) {
        // cout << l << " " << r << endl;
        // cout << v[l] << " " << v[r] << endl;
        // cout << ok << endl << endl;
        if(ok == t) {
            resp = min(resp, r - l + 1);
            cnt[v[l]]--;
            if(need[v[l]] and cnt[v[l]] < need[v[l]] and okay[v[l]]) {
                ok--;
                okay[v[l]] = false;
            }
            l++;
        } else {
            r++;
            cnt[v[r]]++;
            if(need[v[r]] and cnt[v[r]] >= need[v[r]] and !okay[v[r]]) {
                ok++;
                okay[v[r]] = true;
            }
        }
    }
    if(resp == INF) cout << "impossible" << endl;
    else cout << resp << endl;

    return 0;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2004 KB Output is correct
2 Correct 2 ms 2092 KB Output is correct
3 Correct 3 ms 2004 KB Output is correct
4 Correct 2 ms 2092 KB Output is correct
5 Correct 3 ms 2004 KB Output is correct
6 Correct 3 ms 2084 KB Output is correct
7 Correct 2 ms 2004 KB Output is correct
8 Correct 2 ms 2004 KB Output is correct
9 Correct 2 ms 2088 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2132 KB Output is correct
2 Correct 2 ms 2132 KB Output is correct
3 Correct 2 ms 2132 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Correct 2 ms 2100 KB Output is correct
6 Correct 2 ms 2132 KB Output is correct
7 Correct 1 ms 2088 KB Output is correct
8 Correct 2 ms 2004 KB Output is correct
9 Correct 2 ms 2004 KB Output is correct
10 Correct 2 ms 2092 KB Output is correct
11 Correct 1 ms 2004 KB Output is correct
12 Correct 1 ms 2004 KB Output is correct
13 Correct 1 ms 2004 KB Output is correct
14 Correct 1 ms 2084 KB Output is correct
15 Correct 1 ms 2004 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 3924 KB Output is correct
2 Correct 12 ms 4032 KB Output is correct
3 Correct 14 ms 4052 KB Output is correct
4 Correct 13 ms 4012 KB Output is correct
5 Correct 19 ms 4780 KB Output is correct
6 Correct 14 ms 4016 KB Output is correct
7 Correct 13 ms 4144 KB Output is correct
8 Correct 19 ms 4964 KB Output is correct
9 Correct 16 ms 4564 KB Output is correct
10 Correct 13 ms 4024 KB Output is correct
11 Correct 2 ms 2132 KB Output is correct
12 Correct 2 ms 2100 KB Output is correct
13 Correct 2 ms 2132 KB Output is correct
14 Correct 2 ms 2132 KB Output is correct
15 Correct 2 ms 2132 KB Output is correct
16 Correct 2 ms 2132 KB Output is correct
17 Correct 1 ms 2092 KB Output is correct
18 Correct 2 ms 2092 KB Output is correct
19 Correct 1 ms 2088 KB Output is correct
20 Correct 2 ms 2004 KB Output is correct
21 Correct 1 ms 2004 KB Output is correct
22 Correct 2 ms 2004 KB Output is correct
23 Correct 1 ms 2004 KB Output is correct
24 Correct 2 ms 2004 KB Output is correct
25 Correct 1 ms 2088 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 6052 KB Output is correct
2 Correct 31 ms 5708 KB Output is correct
3 Correct 21 ms 5332 KB Output is correct
4 Correct 12 ms 3924 KB Output is correct
5 Correct 32 ms 6504 KB Output is correct
6 Correct 37 ms 7116 KB Output is correct
7 Correct 22 ms 4640 KB Output is correct
8 Correct 20 ms 4948 KB Output is correct
9 Correct 12 ms 3924 KB Output is correct
10 Correct 12 ms 3924 KB Output is correct
11 Correct 13 ms 4052 KB Output is correct
12 Correct 13 ms 4044 KB Output is correct
13 Correct 17 ms 4764 KB Output is correct
14 Correct 11 ms 4020 KB Output is correct
15 Correct 13 ms 4180 KB Output is correct
16 Correct 21 ms 4848 KB Output is correct
17 Correct 16 ms 4556 KB Output is correct
18 Correct 13 ms 4036 KB Output is correct
19 Correct 1 ms 2088 KB Output is correct
20 Correct 1 ms 2132 KB Output is correct
21 Correct 2 ms 2100 KB Output is correct
22 Correct 3 ms 2104 KB Output is correct
23 Correct 2 ms 2132 KB Output is correct
24 Correct 2 ms 2132 KB Output is correct
25 Correct 1 ms 2004 KB Output is correct
26 Correct 1 ms 2088 KB Output is correct
27 Correct 2 ms 2088 KB Output is correct
28 Correct 1 ms 2004 KB Output is correct
29 Correct 1 ms 2004 KB Output is correct
30 Correct 2 ms 2088 KB Output is correct
31 Correct 1 ms 2004 KB Output is correct
32 Correct 2 ms 2004 KB Output is correct
33 Correct 2 ms 2132 KB Output is correct