Submission #1302185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302185		regulardude6	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	69 ms	29352 KiB

hieroglyphs

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

static const int V = 200002;
static const int INF = 1000000007;

struct SegMin {
    int n;
    vector<int> st;
    void init(int N){
        n = N;
        st.assign(4*n+4, INF);
    }
    void upd(int p, int l, int r, int idx, int val){
        if(l==r){ st[p] = min(st[p], val); return; }
        int m=(l+r)>>1;
        if(idx<=m) upd(p<<1,l,m,idx,val);
        else upd(p<<1|1,m+1,r,idx,val);
        st[p]=min(st[p<<1],st[p<<1|1]);
    }
    int ql(int p,int l,int r,int q){
        if(q>=r) return st[p];
        int m=(l+r)>>1;
        if(q<=m) return min(ql(p<<1,l,m,q), st[p<<1|1]);
        return ql(p<<1|1,m+1,r,q);
    }
    int qr(int p,int l,int r,int q){
        if(q<=l) return st[p];
        int m=(l+r)>>1;
        if(q>m) return min(st[p<<1], qr(p<<1|1,m+1,r,q));
        return qr(p<<1,l,m,q);
    }
};

static SegMin seg;

static inline bool is_sq(const vector<int>& Ax, const vector<int>& Ay,
                         const vector<int>& Bx, const vector<int>& By,
                         int k, int l){
    if((int)Ax.size() < k || (int)Ay.size() < l) return false;
    if((int)Bx.size() < k || (int)By.size() < l) return false;
    int ax = Ax[k-1], ay = Ay[(int)Ay.size()-l];
    int bx = Bx[k-1], by = By[(int)By.size()-l];
    return ax < ay && bx < by;
}

vector<int> ucs(vector<int> A, vector<int> B) {
    int N = (int)A.size(), M = (int)B.size();
    vector<vector<int>> posA(V), posB(V);
    vector<int> ca(V,0), cb(V,0);
    for(int i=0;i<N;i++){ int x=A[i]; if(0<=x && x<V){ ca[x]++; posA[x].push_back(i); } }
    for(int i=0;i<M;i++){ int x=B[i]; if(0<=x && x<V){ cb[x]++; posB[x].push_back(i); } }

    vector<char> common(V,0), weakA(V,0);
    for(int x=0;x<V;x++){
        if(ca[x] && cb[x]){
            common[x]=1;
            weakA[x] = (ca[x] <= cb[x]);
        }
    }

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

    vector<int> used(V,0);
    vector<int> E;
    E.reserve(C.size() + D.size());

    int i=0,j=0;
    while(i < (int)C.size() || j < (int)D.size()){
        if(!E.empty()) used[E.back()]++;

        if(i==(int)C.size()){ E.push_back(D[j++]); continue; }
        if(j==(int)D.size()){ E.push_back(C[i++]); continue; }

        int x = C[i], y = D[j];

        if(ca[x]==cb[x] || ca[y]==cb[y]){
            if(x==y){ E.push_back(x); i++; j++; continue; }
            if(ca[x]!=cb[x]){ E.push_back(x); i++; continue; }
            if(ca[y]!=cb[y]){ E.push_back(y); j++; continue; }
            return vector<int>{-1};
        }

        int kx = used[x] + 1;
        int ly = cb[y] - used[y];
        int ky = used[y] + 1;
        int lx = ca[x] - used[x];

        bool X = is_sq(posA[x], posA[y], posB[x], posB[y], kx, ly);
        bool Y = is_sq(posA[y], posA[x], posB[y], posB[x], ky, lx);

        if(X && Y) return vector<int>{-1};
        if(Y){ E.push_back(y); j++; }
        else if(X){ E.push_back(x); i++; }
        else return vector<int>{-1};
    }

    int L = (int)E.size();
    vector<int> fA1(L), fA2(L), fB1(L), fB2(L);

    {
        int p=0;
        for(int t=0;t<L;t++){
            while(p<N && A[p]!=E[t]) p++;
            if(p==N) return vector<int>{-1};
            fA1[t]=p++;
        }
        p=N-1;
        for(int t=L-1;t>=0;t--){
            while(p>=0 && A[p]!=E[t]) p--;
            if(p<0) return vector<int>{-1};
            fA2[t]=p--;
        }
    }
    {
        int p=0;
        for(int t=0;t<L;t++){
            while(p<M && B[p]!=E[t]) p++;
            if(p==M) return vector<int>{-1};
            fB1[t]=p++;
        }
        p=M-1;
        for(int t=L-1;t>=0;t--){
            while(p>=0 && B[p]!=E[t]) p--;
            if(p<0) return vector<int>{-1};
            fB2[t]=p--;
        }
    }

    vector<int> last(V,-1), prv(L,-1);
    for(int t=0;t<L;t++){
        int x=E[t];
        prv[t]=last[x];
        last[x]=t;
    }

    auto build_side = [&](const vector<int>& S, int n, const vector<vector<int>>& pos, bool rev)->vector<int>{
        int m=(int)S.size();
        int SZ=1; while(SZ<m) SZ<<=1;
        vector<int> segv(2*SZ, INF);
        auto seg_set = [&](int idx,int val){
            int p=idx+SZ; segv[p]=val;
            for(p>>=1;p;p>>=1) segv[p]=min(segv[p<<1],segv[p<<1|1]);
        };
        auto seg_q = [&](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, segv[l++]);
                if(!(r&1)) res=min(res, segv[r--]);
                l>>=1; r>>=1;
            }
            return res;
        };
        vector<int> dp(m, INF);
        for(int t=0;t<m;t++){
            int x=S[t];
            int mp = (prv[t]==-1)? -1 : seg_q(prv[t], t-1);
            if(mp>=INF){
                dp[t]=INF;
            }else{
                const auto &vec=pos[x];
                if(!rev){
                    auto it = upper_bound(vec.begin(), vec.end(), mp);
                    dp[t] = (it==vec.end()? INF : *it);
                }else{
                    int bound = (n-1) - mp;
                    auto it = lower_bound(vec.begin(), vec.end(), bound);
                    if(it==vec.begin()) dp[t]=INF;
                    else { --it; dp[t]=(n-1)-*it; }
                }
            }
            seg_set(t, dp[t]);
        }
        return dp;
    };

    vector<int> VL_A = build_side(E, N, posA, false);
    vector<int> VL_B = build_side(E, M, posB, false);

    vector<int> Er = E;
    reverse(Er.begin(), Er.end());
    vector<int> VLAr = build_side(Er, N, posA, true);
    vector<int> VLBr = build_side(Er, M, posB, true);

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

    vector<int> wL(L), wR(L);
    for(int t=0;t<L;t++){
        int x=E[t];
        if(weakA[x]){ wL[t]=fA1[t]; wR[t]=fA2[t]; }
        else { wL[t]=fB1[t]; wR[t]=fB2[t]; }
    }

    seg.init(N+2);
    for(int t=0;t<L;t++){
        int x=E[t];
        if(!weakA[x]){
            int q = seg.qr(1,1,seg.n, VL_A[t]+2);
            if(q < wL[t]) return vector<int>{-1};
        }
        if(weakA[x] && VR_B[t]!=-1){
            seg.upd(1,1,seg.n, wR[t]+1, (seg.n-1)-VR_B[t]);
        }
    }

    seg.init(M+2);
    for(int t=0;t<L;t++){
        int x=E[t];
        if(weakA[x]){
            int q = seg.qr(1,1,seg.n, VL_B[t]+2);
            if(q < wL[t]) return vector<int>{-1};
        }
        if(!weakA[x] && VR_A[t]!=-1){
            seg.upd(1,1,seg.n, wR[t]+1, (seg.n-1)-VR_A[t]);
        }
    }

    return E;
}

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