oj.uz

답안 #855988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855988 2023-10-02T13:33:44 Z RiverFlow Martian DNA (BOI18_dna) C++14
100 / 100
 105 ms 141376 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

int a[N], cnt[12][N], b[N], q[N], ind[N];

int n, k, r;

bool check(int x, int y) {
    FOR(i, 1, r)
        if (cnt[i][y] - cnt[i][x - 1] < q[i]) return 0;
    return 1;
}

void subtask3() {
    FOR(j, 1, r) {
        FOR(i, 1, n) cnt[j][i] = cnt[j][i - 1] + (a[i] == j);
    }
    int res = n + 1, j = 1;
    FOR(i, 1, n) {
        while (j <= i and check(j, i)) {
            res = min(res, i - j + 1); ++j;
        }
    }
    if (res == n + 1)
        evoid("impossible");
    cout << res;
}

int c[N];

queue<int> pos[N];

bool ok[N];

void main_code() {
    cin >> n >> k >> r;
    FOR(i, 1, n) cin >> a[i], ++a[i];

    FOR(i, 1, r) cin >> b[i] >> q[i], ++b[i];

    FOR(i, 1, r) ind[b[i]] = i; ind[0] = 0;

    FOR(i, 1, n) a[i] = ind[ a[i] ];

//    if (r <= 10) return subtask3(), void();

    int j = 1, d = 0, ans = n + 1;

    FOR(i, 1, n) {
        int v = a[i]; if (v == 0) continue ;
        pos[v].push(i);
        d -= ok[v];
        ok[v] |= sz(pos[v]) == q[v];
        d += ok[v];
        while (j <= i) {
            if (a[j] == 0) {
                ++j; continue ;
            }
            assert(pos[a[j]].size());
            if (sz(pos[a[j]]) > q[a[j]]) {
                pos[a[j]].pop(); ++j;
            } else
                break ;
        }
        while (sz(pos[v]) > q[v] and pos[v].front() <= j) {
            pos[v].pop(); ++j;
            while (j <= i) {
                if (a[j] == 0) {
                    ++j; continue ;
                }
                if (sz(pos[a[j]]) > q[a[j]]) {
                    pos[a[j]].pop(); ++j;
                } else
                    break ;
            }
        }
//        cout << i << ' ' << j << ' ' << ans << nl;

        if (d == r) {
            ans = min(ans, i - j + 1);
        }
    }

    if (ans == n + 1)
        evoid("impossible");

    cout << ans;
}


/*     Let the river flows naturally     */

Compilation message

dna.cpp: In function 'void main_code()':
dna.cpp:15:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   15 | #define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
      |                      ^~~
dna.cpp:83:5: note: in expansion of macro 'FOR'
   83 |     FOR(i, 1, r) ind[b[i]] = i; ind[0] = 0;
      |     ^~~
dna.cpp:83:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   83 |     FOR(i, 1, r) ind[b[i]] = i; ind[0] = 0;
      |                                 ^~~
dna.cpp: In function 'int main()':
dna.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 139944 KB Output is correct
2 Correct 68 ms 139856 KB Output is correct
3 Correct 68 ms 139860 KB Output is correct
4 Correct 69 ms 139832 KB Output is correct
5 Correct 67 ms 139856 KB Output is correct
6 Correct 67 ms 139928 KB Output is correct
7 Correct 69 ms 139868 KB Output is correct
8 Correct 86 ms 139724 KB Output is correct
9 Correct 69 ms 139856 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 139944 KB Output is correct
2 Correct 78 ms 139856 KB Output is correct
3 Correct 68 ms 139860 KB Output is correct
4 Correct 69 ms 139876 KB Output is correct
5 Correct 70 ms 140036 KB Output is correct
6 Correct 84 ms 139948 KB Output is correct
7 Correct 69 ms 139940 KB Output is correct
8 Correct 67 ms 139936 KB Output is correct
9 Correct 68 ms 139840 KB Output is correct
10 Correct 68 ms 139860 KB Output is correct
11 Correct 77 ms 139888 KB Output is correct
12 Correct 68 ms 139696 KB Output is correct
13 Correct 68 ms 139948 KB Output is correct
14 Correct 83 ms 139864 KB Output is correct
15 Correct 69 ms 139860 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 140616 KB Output is correct
2 Correct 86 ms 140340 KB Output is correct
3 Correct 79 ms 140116 KB Output is correct
4 Correct 90 ms 140372 KB Output is correct
5 Correct 82 ms 140196 KB Output is correct
6 Correct 84 ms 140884 KB Output is correct
7 Correct 86 ms 140204 KB Output is correct
8 Correct 85 ms 140092 KB Output is correct
9 Correct 77 ms 140116 KB Output is correct
10 Correct 87 ms 140536 KB Output is correct
11 Correct 68 ms 139856 KB Output is correct
12 Correct 77 ms 139860 KB Output is correct
13 Correct 69 ms 139952 KB Output is correct
14 Correct 72 ms 139944 KB Output is correct
15 Correct 70 ms 139948 KB Output is correct
16 Correct 69 ms 139860 KB Output is correct
17 Correct 67 ms 139856 KB Output is correct
18 Correct 68 ms 139972 KB Output is correct
19 Correct 82 ms 139860 KB Output is correct
20 Correct 67 ms 139812 KB Output is correct
21 Correct 68 ms 139876 KB Output is correct
22 Correct 69 ms 139860 KB Output is correct
23 Correct 67 ms 139908 KB Output is correct
24 Correct 68 ms 139860 KB Output is correct
25 Correct 69 ms 139944 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 140112 KB Output is correct
2 Correct 96 ms 140136 KB Output is correct
3 Correct 91 ms 140224 KB Output is correct
4 Correct 80 ms 140120 KB Output is correct
5 Correct 98 ms 140080 KB Output is correct
6 Correct 105 ms 140488 KB Output is correct
7 Correct 89 ms 141220 KB Output is correct
8 Correct 86 ms 141244 KB Output is correct
9 Correct 90 ms 140880 KB Output is correct
10 Correct 85 ms 140628 KB Output is correct
11 Correct 80 ms 140564 KB Output is correct
12 Correct 85 ms 140880 KB Output is correct
13 Correct 80 ms 141244 KB Output is correct
14 Correct 84 ms 141376 KB Output is correct
15 Correct 84 ms 140720 KB Output is correct
16 Correct 90 ms 141336 KB Output is correct
17 Correct 79 ms 141008 KB Output is correct
18 Correct 88 ms 140884 KB Output is correct
19 Correct 70 ms 139952 KB Output is correct
20 Correct 89 ms 140080 KB Output is correct
21 Correct 68 ms 139968 KB Output is correct
22 Correct 68 ms 139856 KB Output is correct
23 Correct 69 ms 139912 KB Output is correct
24 Correct 69 ms 139856 KB Output is correct
25 Correct 68 ms 139732 KB Output is correct
26 Correct 68 ms 139892 KB Output is correct
27 Correct 69 ms 139860 KB Output is correct
28 Correct 68 ms 139944 KB Output is correct
29 Correct 78 ms 139948 KB Output is correct
30 Correct 68 ms 139948 KB Output is correct
31 Correct 71 ms 139864 KB Output is correct
32 Correct 70 ms 139864 KB Output is correct
33 Correct 68 ms 139860 KB Output is correct