Submission #378286

#	Time	Username	Problem	Language	Result	Execution time	Memory
378286		Sara	Martian DNA (BOI18_dna)	C++14	100 / 100	347 ms	21484 KiB

dna

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define F first
#define S second

 
const int N = 200000 + 5;
const int LOG = 30;

int n, k, R, a[N];
vector <int> ids[N];
pair <int, int> p[N];

int pntl[N], pntr[N];
vector <int> all[N];
int cnt_ok;

inline int get(int id){
    int ret = 0;
    int x = p[id].F;
    int sz = ids[x].size();
    if (pntl[id] < sz){
        ret = pntr[id] - pntl[id];
    }
    return ret;
}

inline void update_l(int z){
    for (int it : all[z]){
        int bef = get(it);
        pntl[it] ++;
        int aft = get(it);
        if (p[it].S <= bef){
            cnt_ok --;
        }
        if (p[it].S <= aft){
            cnt_ok ++;
        }
    }
    return;
}

inline void update_r(int z){
    for (int it : all[z]){
        int bef = get(it);
        pntr[it] ++;
        int aft = get(it);
        if (p[it].S <= bef){
            cnt_ok --;
        }
        if (p[it].S <= aft){
            cnt_ok ++;
        }
    }
    return; 
}

inline void pre(){
    for (int i = 0; i < R; i ++){
        int x = p[i].F;
        int sz = ids[x].size();
        for (int j = 0; j < sz; j ++){
            all[ids[x][j]].pb(i);
        }
    }
    return;
}

bool ok(int len){

    if (n < len) return 0;
    int strt = 1;
    for (int i = 0; i < R; i ++){
        int x = p[i].F;
        if (ids[x].empty()){
            return 0;
        }
        strt = max(strt, ids[x][0] - len + 1);
        pntl[i] = pntr[i] = 0;
    }

    cnt_ok = 0;
    for (int i = 0; i < R; i ++){
        int x = p[i].F;
        int y = p[i].S;
        int sz = ids[x].size();
        while (pntl[i] < sz && ids[x][pntl[i]] < strt){
            pntl[i] ++;
        }
        while (pntr[i] < sz && ids[x][pntr[i]] <= strt + len - 1){
            pntr[i] ++;
        }
        if (y <= get(i)){
            cnt_ok ++;
        }
    }

    if (cnt_ok == R){
        return 1;
    }

    for (int l = strt + 1; l + len - 1 <= n; l ++){
        int r = l + len - 1;
        update_l(l - 1);
        update_r(r);
        if (cnt_ok == R){
            return 1;
        }
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
    cin >> n >> k >> R;
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
        ids[a[i]].pb(i);
    }
    for (int i = 0; i < R; i ++){
        cin >> p[i].F >> p[i].S;
    }
    pre();
    int l = 0, r = n + 1;
    while (l + 1 < r){
        int mid = (l + r) / 2;
        if (ok(mid)){
            r = mid;
        }
        else {
            l = mid;
        }
    }
    if (r == n + 1){
        cout << "impossible\n";
    }
    else {
        cout << r << '\n';
    }
    return 0;
}

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