Submission #222368

#	Time	Username	Problem	Language	Result	Execution time	Memory
222368		lyc	Grudanje (COCI19_grudanje)	C++14	70 / 70	916 ms	11640 KiB

grudanje

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

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 1e5+5;
const int MX_Q = 1e5+5;

string S;
int N, Q, A[MX_Q], B[MX_Q], P[MX_N];
int nxt[MX_N], pos[26];

struct node {
    int s, e, m, v;
    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2), v(0) {
        if (s != e) {
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }

    void update(int i, int x) {
        if (s == e) { v = x; return; }
        if (i <= m) l->update(i,x);
        else r->update(i,x);
        v = min(l->v,r->v);
    }

    int query(int x, int y) {
        if (s == x && e == y) return v;
        else if (y <= m) return l->query(x,y);
        else if (x >  m) return r->query(x,y);
        else return min(l->query(x,m),r->query(m+1,y));
    }
} *root;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> S; N = S.length();
    cin >> Q;
    FOR(i,1,Q){
        cin >> A[i] >> B[i];
        --A[i], --B[i];
    }
    FOR(i,1,N){
        cin >> P[i];
        --P[i];
    }

    root = new node(0,N-1);
    int lo = -1, hi = N;
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;

        string T(S);
        FOR(i,0,mid) T[P[i]] = '#';
        FOR(i,0,25) pos[i] = N;
        RFOR(i,N-1,0){
            if (T[i] == '#') nxt[i] = N;
            else {
                nxt[i] = pos[T[i]-'a'];
                pos[T[i]-'a'] = i;
            }
            root->update(i,nxt[i]);
        }
        bool ok = 1;
        FOR(i,1,Q){
            ok &= root->query(A[i],B[i]) > B[i];
        }
        //FOR(i,0,N-1) cout << nxt[i] << ' ';
        //cout << endl;
        //cout << "pos i " << mid << " :: " << ok << endl;

        if (ok) hi = mid;
        else lo = mid;
    }
    cout << lo+1 << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7