Submission #1302189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302189		regulardude6	Hieroglyphs (IOI24_hieroglyphs)	C++20	100 / 100	110 ms	45088 KiB

hieroglyphs

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

static const int SIG = 200001;
static const int INF = 1e9;

struct BITMax {
    int n;
    vector<int> bit;
    BITMax(int n=0){ init(n); }
    void init(int n_){
        n = n_;
        bit.assign(n+1, -1);
    }
    void upd(int pos, int val){
        int i = n - pos;
        for(; i <= n; i += i & -i) bit[i] = max(bit[i], val);
    }
    int query_suffix_gt(int th){
        if(th >= n-1) return -1;
        int lim = n - (th+1);
        int res = -1;
        for(int i = lim; i > 0; i -= i & -i) res = max(res, bit[i]);
        return res;
    }
};

static inline int next_pos(const vector<int>& v, int after){
    auto it = upper_bound(v.begin(), v.end(), after);
    if(it == v.end()) return INF;
    return *it;
}

static vector<int> compute_VL(const vector<int>& S, const vector<vector<int>>& posS, const vector<int>& T){
    int n = (int)S.size();
    int m = (int)T.size();
    vector<int> prev(m, -1);
    static vector<int> last(SIG, -1);
    for(int i=0;i<SIG;i++) last[i] = -1;
    for(int i=0;i<m;i++){
        int c = T[i];
        prev[i] = last[c];
        last[c] = i;
    }
    int SZ = 1;
    while(SZ < m) SZ <<= 1;
    vector<int> seg(2*SZ, INF);
    auto seg_set = [&](int idx, int val){
        int p = idx + SZ;
        seg[p] = val;
        for(p >>= 1; p; p >>= 1) seg[p] = min(seg[p<<1], seg[p<<1|1]);
    };
    auto seg_min = [&](int l, int r){
        if(l > r) return INF;
        l += SZ; r += SZ;
        int res = INF;
        while(l <= r){
            if(l & 1) res = min(res, seg[l++]);
            if(!(r & 1)) res = min(res, seg[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    };

    vector<int> dp(m, INF);
    for(int i=0;i<m;i++){
        int c = T[i];
        int bestPrev;
        if(prev[i] == -1){
            bestPrev = min(-1, (i==0 ? INF : seg_min(0, i-1)));
        } else {
            bestPrev = seg_min(prev[i], i-1);
        }
        if(bestPrev >= INF) dp[i] = INF;
        else dp[i] = next_pos(posS[c], bestPrev);
        seg_set(i, dp[i]);
    }
    return dp;
}

static vector<int> compute_VR(const vector<int>& S, const vector<vector<int>>& posSr, const vector<int>& T){
    int n = (int)S.size();
    int m = (int)T.size();
    vector<int> Tr = T;
    reverse(Tr.begin(), Tr.end());
    vector<int> VLr = compute_VL(vector<int>(), posSr, Tr);
    vector<int> VR(m, -1);
    for(int i=0;i<m;i++){
        int x = VLr[m-1-i];
        if(x >= INF) VR[i] = -1;
        else VR[i] = n-1-x;
    }
    return VR;
}

static bool embed_left(const vector<int>& P, const vector<int>& S, vector<int>& out){
    out.resize(P.size());
    int p = 0;
    for(int i=0;i<(int)P.size();i++){
        int x = P[i];
        while(p < (int)S.size() && S[p] != x) p++;
        if(p == (int)S.size()) return false;
        out[i] = p++;
    }
    return true;
}

static bool embed_right(const vector<int>& P, const vector<int>& S, vector<int>& out){
    out.resize(P.size());
    int p = (int)S.size()-1;
    for(int i=(int)P.size()-1;i>=0;i--){
        int x = P[i];
        while(p >= 0 && S[p] != x) p--;
        if(p < 0) return false;
        out[i] = p--;
    }
    return true;
}

static inline bool block_common(
    int x, int kx, int y, int ly,
    const vector<vector<int>>& posA, const vector<vector<int>>& posB
){
    const auto &Ax = posA[x], &Ay = posA[y];
    const auto &Bx = posB[x], &By = posB[y];
    if((int)Ax.size() < kx || (int)Ay.size() < ly) return false;
    if((int)Bx.size() < kx || (int)By.size() < ly) return false;
    int ax = Ax[kx-1];
    int ay = Ay[(int)Ay.size() - ly];
    int bx = Bx[kx-1];
    int by = By[(int)By.size() - ly];
    return ax < ay && bx < by;
}

vector<int> ucs(vector<int> A, vector<int> B) {
    int N = (int)A.size(), M = (int)B.size();

    vector<int> occA(SIG,0), occB(SIG,0);
    vector<vector<int>> posA(SIG), posB(SIG);
    vector<char> inA(SIG,0), inB(SIG,0);

    for(int i=0;i<N;i++){
        int x = A[i];
        if(0<=x && x<SIG){
            occA[x]++; posA[x].push_back(i); inA[x]=1;
        }
    }
    for(int i=0;i<M;i++){
        int x = B[i];
        if(0<=x && x<SIG){
            occB[x]++; posB[x].push_back(i); inB[x]=1;
        }
    }

    vector<char> common(SIG,0), aweak(SIG,0);
    for(int x=0;x<SIG;x++){
        if(inA[x] && inB[x]){
            common[x]=1;
            aweak[x] = (occA[x] <= occB[x]);
        }
    }

    vector<int> WA, WB;
    WA.reserve(N); WB.reserve(M);
    for(int x: A) if(common[x] && aweak[x]) WA.push_back(x);
    for(int x: B) if(common[x] && !aweak[x]) WB.push_back(x);

    vector<int> usedA(SIG,0), usedB(SIG,0);
    vector<int> C;
    C.reserve(WA.size() + WB.size());

    int i=0, j=0;
    while(i < (int)WA.size() && j < (int)WB.size()){
        int x = WA[i], y = WB[j];
        int k1 = usedA[x] + 1;
        int l1 = occB[y] - usedB[y];
        int k2 = usedB[y] + 1;
        int l2 = occA[x] - usedA[x];

        bool ok1 = block_common(x, k1, y, l1, posA, posB);
        bool ok2 = block_common(y, k2, x, l2, posA, posB);

        if(ok1 ^ ok2){
            if(ok1){ C.push_back(x); usedA[x]++; i++; }
            else { C.push_back(y); usedB[y]++; j++; }
        } else {
            return vector<int>{-1};
        }
    }
    while(i < (int)WA.size()) C.push_back(WA[i++]);
    while(j < (int)WB.size()) C.push_back(WB[j++]);

    vector<int> LA, LB, RA, RB;
    if(!embed_left(C, A, LA)) return vector<int>{-1};
    if(!embed_left(C, B, LB)) return vector<int>{-1};
    if(!embed_right(C, A, RA)) return vector<int>{-1};
    if(!embed_right(C, B, RB)) return vector<int>{-1};

    int L = (int)C.size();
    vector<int> wL(L), wR(L);
    for(int t=0;t<L;t++){
        int x = C[t];
        if(aweak[x]){ wL[t] = LA[t]; wR[t] = RA[t]; }
        else { wL[t] = LB[t]; wR[t] = RB[t]; }
    }

    vector<vector<int>> posAr(SIG), posBr(SIG);
    for(int x=0;x<SIG;x++){
        if(!posA[x].empty()){
            posAr[x].reserve(posA[x].size());
            for(int p: posA[x]) posAr[x].push_back(N-1-p);
            sort(posAr[x].begin(), posAr[x].end());
        }
        if(!posB[x].empty()){
            posBr[x].reserve(posB[x].size());
            for(int p: posB[x]) posBr[x].push_back(M-1-p);
            sort(posBr[x].begin(), posBr[x].end());
        }
    }

    vector<int> VL_A = compute_VL(A, posA, C);
    vector<int> VL_B = compute_VL(B, posB, C);

    vector<int> Cr = C; reverse(Cr.begin(), Cr.end());
    vector<int> VL_Ar = compute_VL(vector<int>(), posAr, Cr);
    vector<int> VL_Br = compute_VL(vector<int>(), posBr, Cr);

    vector<int> VR_A(L, -1), VR_B(L, -1);
    for(int t=0;t<L;t++){
        int a = VL_Ar[L-1-t];
        int b = VL_Br[L-1-t];
        VR_A[t] = (a >= INF ? -1 : N-1-a);
        VR_B[t] = (b >= INF ? -1 : M-1-b);
    }

    BITMax bitA(N), bitB(M);

    for(int t=0;t<L;t++){
        int x = C[t];
        if(!aweak[x]){
            int th = VL_A[t];
            if(th < INF){
                int best = bitA.query_suffix_gt(th);
                if(best > wL[t]) return vector<int>{-1};
            }
        }
        if(aweak[x] && VR_B[t] != -1){
            bitA.upd(wR[t], VR_B[t]);
        }
    }

    for(int t=0;t<L;t++){
        int x = C[t];
        if(aweak[x]){
            int th = VL_B[t];
            if(th < INF){
                int best = bitB.query_suffix_gt(th);
                if(best > wL[t]) return vector<int>{-1};
            }
        }
        if(!aweak[x] && VR_A[t] != -1){
            bitB.upd(wR[t], VR_A[t]);
        }
    }

    return C;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 16 / 16
• Subtask 5: 14 / 14
• Subtask 6: 42 / 42