Submission #1090589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090589		gyg	Martian DNA (BOI18_dna)	C++17	100 / 100	335 ms	13908 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define arr array
#define pii pair<int, int>
const int MX_N = 2e5 + 5, INF = 1e9;
 
int n;
arr<int, MX_N> vl, rq;

arr<int, MX_N> scr;
set<pii> ord;
void upd(int i, int x) {
    ord.erase({scr[i], i});
    scr[i] += x;
    ord.insert({scr[i], i});
}
int cmp() {
    for (int i = 1; i <= n; i++) scr[i] = -rq[i];
    for (int i = 1; i <= n; i++) ord.insert({scr[i], i});

    int ans = INF, r = 0;
    for (int l = 1; l <= n; l++) {
        while (r != n && (r < l || ord.begin()->first < 0)) {
            r++;
            upd(vl[r], 1);
        }
        if (ord.begin()->first >= 0) ans = min(ans, r - l + 1);
        upd(vl[l], -1);
    }
    return ans;
}
 
int main() {
    // freopen("mrt.in", "r", stdin);
    int tmp1, tmp2; cin >> n >> tmp1 >> tmp2;
    for (int i = 1; i <= n; i++) { cin >> vl[i]; vl[i]++; }
    for (int i = 1; i <= tmp2; i++) { int x; cin >> x; cin >> rq[x + 1]; }
 
    int ans = cmp();
    if (ans == INF) cout << "impossible" << endl;
    else cout << ans << endl;
}

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