답안 #446480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446480	2021-07-22T05:40:19 Z	dxz05	Martian DNA (BOI18_dna)	C++14	100 / 100	68 ms	4560 KB

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define revall(x) (x).rbegin(), (x).rend()

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 2e5 + 3e2;
const int M = 222;

int a[N];
int diff = 0;
int cnt[N], need[N];

void add(int i){
    int x = a[i];
    if (need[x] == 0) return;
    cnt[x]++;
    if (cnt[x] == need[x]) diff++;
}

void del(int i){
    int x = a[i];
    if (need[x] == 0) return;
    cnt[x]--;
    if (cnt[x] == need[x] - 1) diff--;
}

int n, k, q;

bool check(int len){
    fill(cnt, cnt + k, 0);
    diff = 0;
    for (int i = 1; i <= n; i++){
        add(i);
        if (i > len) del(i - len);
        if (diff == q) return true;
    }
    return false;
}

void solve(int TC) {
    cin >> n >> k >> q;

    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= q; i++){
        int x, y;
        cin >> x >> y;
        need[x] = y;
    }

    int ans = -1;
    int l = 1, r = n;
    while (l <= r){
        int m = (l + r) >> 1;
        if (check(m)){
            ans = m;
            r = m - 1;
        } else l = m + 1;
    }

    if (ans == -1) cout << "impossible"; else
        cout << ans;

}

int main() {
    startTime = clock();
    cin.tie(nullptr); cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    //cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	0 ms	216 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	1488 KB	Output is correct
2	Correct	40 ms	1484 KB	Output is correct
3	Correct	22 ms	1508 KB	Output is correct
4	Correct	33 ms	1532 KB	Output is correct
5	Correct	28 ms	2500 KB	Output is correct
6	Correct	29 ms	1476 KB	Output is correct
7	Correct	27 ms	1612 KB	Output is correct
8	Correct	32 ms	3148 KB	Output is correct
9	Correct	24 ms	2124 KB	Output is correct
10	Correct	34 ms	1484 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	0 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	1 ms	320 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct

Subtask #4
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	3484 KB	Output is correct
2	Correct	52 ms	3140 KB	Output is correct
3	Correct	46 ms	2808 KB	Output is correct
4	Correct	14 ms	1484 KB	Output is correct
5	Correct	68 ms	4040 KB	Output is correct
6	Correct	64 ms	4560 KB	Output is correct
7	Correct	37 ms	2124 KB	Output is correct
8	Correct	54 ms	2400 KB	Output is correct
9	Correct	32 ms	1484 KB	Output is correct
10	Correct	40 ms	1440 KB	Output is correct
11	Correct	22 ms	1540 KB	Output is correct
12	Correct	33 ms	1400 KB	Output is correct
13	Correct	28 ms	2508 KB	Output is correct
14	Correct	28 ms	1476 KB	Output is correct
15	Correct	26 ms	1652 KB	Output is correct
16	Correct	33 ms	3192 KB	Output is correct
17	Correct	24 ms	2096 KB	Output is correct
18	Correct	34 ms	1484 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	0 ms	332 KB	Output is correct
26	Correct	0 ms	332 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	324 KB	Output is correct
29	Correct	0 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	0 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	332 KB	Output is correct

답안 #446480

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 28.0 / 28.0

Subtask #4 32.0 / 32.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
28.0 / 28.0

Subtask #4
32.0 / 32.0