Submission #1115147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115147		rqi	Hieroglyphs (IOI24_hieroglyphs)	C++17	18 / 100	169 ms	26964 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using db = long double; // or double if tight TL
using str = string;

using pi = pair<int,int>;
#define mp make_pair
#define f first
#define s second

#define tcT template<class T
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pi>;

#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define pb push_back
#define ft front()
#define bk back()

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)

const int MOD = 1e9+7;
const db PI = acos((db)-1);
mt19937 rng(0); // or mt19937_64

tcT> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; } // set a = max(a,b)

tcT, class U> T fstTrue(T lo, T hi, U f) {
    ++hi; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        T mid = lo+(hi-lo)/2;
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}



const int mx = 200005;

/**
 * Description: 1D point update, range query where \texttt{cmb} is
     * any associative operation. If $N=2^p$ then \texttt{seg[1]==query(0,N-1)}.
 * Time: O(\log N)
 * Source: 
    * http://codeforces.com/blog/entry/18051
    * KACTL
 * Verification: SPOJ Fenwick
 */

tcT> struct SegTree { // cmb(ID,b) = b
    const T ID = -MOD; T cmb(T a, T b) { return max(a, b); } 
    int n; V<T> seg;
    void init(int _n) { // upd, query also work if n = _n
        for (n = 1; n < _n; ) n *= 2; 
        seg.assign(2*n,ID); }
    void pull(int p) { seg[p] = cmb(seg[2*p],seg[2*p+1]); }
    void upd(int p, T val) { // set val at position p
        seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
    T query(int l, int r) {    // associative op on [l, r]
        T ra = ID, rb = ID;
        if(l > r) return ID;
        for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
            if (l&1) ra = cmb(ra,seg[l++]);
            if (r&1) rb = cmb(seg[--r],rb);
        }
        return cmb(ra,rb);
    }
    /// int first_at_least(int lo, int val, int ind, int l, int r) { // if seg stores max across range
    ///     if (r < lo || val > seg[ind]) return -1;
    ///     if (l == r) return l;
    ///     int m = (l+r)/2;
    ///     int res = first_at_least(lo,val,2*ind,l,m); if (res != -1) return res;
    ///     return first_at_least(lo,val,2*ind+1,m+1,r);
    /// }
};

bool checkSubseq(vi subseq, vi A){
    int subseq_ind = 0;
    for(auto u: A){
        if(subseq_ind >= sz(subseq)) break;
        if(u == subseq[subseq_ind]){
            subseq_ind++;
        }
    }
    if(subseq_ind >= sz(subseq)) return true;
    return false;
}

vi ucs(vi A, vi B) {
    int N = sz(A);
    int M = sz(B);
    vector<pair<int, vi>> special_As, special_Bs;
    {
        map<int, array<vi, 2>> at_poses;
        for(int i = 0; i < N; i++){
            at_poses[A[i]][0].pb(i);
        }
        for(int i = 0; i < M; i++){
            at_poses[B[i]][1].pb(i);
        }
        for(auto u: at_poses){
            if(sz(u.s[0]) == 0 || sz(u.s[1]) == 0) continue; //irrelevant

            assert(sz(u.s[0]) == 1 || sz(u.s[1]) == 1);
            if(sz(u.s[0]) == 1){
                special_As.pb(mp(u.s[0][0], u.s[1]));
            }
            else{
                special_Bs.pb(mp(u.s[1][0], u.s[0]));
            }
        }
    }
    sort(all(special_As));
    sort(all(special_Bs));

    int A_ind = 0;
    int B_ind = 0;

    vector<pair<char, int>> ord;
    while(A_ind < sz(special_As) || B_ind < sz(special_Bs)){
        if(A_ind == sz(special_As)){
            ord.pb(mp('B', B_ind)); B_ind++; continue;
        }
        if(B_ind == sz(special_Bs)){
            ord.pb(mp('A', A_ind)); A_ind++; continue;
        }

        bool A_before = special_As[A_ind].f < special_Bs[B_ind].s.bk && special_As[A_ind].s[0] < special_Bs[B_ind].f;
        bool B_before = special_Bs[B_ind].f < special_As[A_ind].s.bk && special_Bs[B_ind].s[0] < special_As[A_ind].f;
        if(A_before && B_before){
            return vi{-1};
        }
        if(!A_before && !B_before){
            return vi{-1};
        }

        if(A_before){
            ord.pb(mp('A', A_ind)); A_ind++; continue;
        }
        assert(B_before);
        ord.pb(mp('B', B_ind)); B_ind++; continue;
    }

    SegTree<int> A_max_to, B_max_to;
    A_max_to.init(N);
    B_max_to.init(M);

    // for(int i = 0; i < sz(special_As); i++){
    //     A_max_to.upd(special_As[i].f, special_As[i].s.bk);
    // }
    // for(int i = 0; i < sz(special_Bs); i++){
    //     B_max_to.upd(special_Bs[i].f, special_Bs[i].s.bk);
    // }

    for(auto [side, ind]: ord){
        if(side == 'A'){
            if(B_max_to.query(special_As[ind].s[0], special_As[ind].s.bk) > special_As[ind].f){
                return vi{-1};
            }
            A_max_to.upd(special_As[ind].f, special_As[ind].s.bk);
        }
        else{
            if(A_max_to.query(special_Bs[ind].s[0], special_Bs[ind].s.bk) > special_Bs[ind].f){
                return vi{-1};
            }
            B_max_to.upd(special_Bs[ind].f, special_Bs[ind].s.bk);
        }
    }

    vi ans;
    for(auto [side, ind]: ord){
        if(side == 'A'){
            ans.pb(A[special_As[ind].f]);
        }
        else{
            ans.pb(B[special_Bs[ind].f]);
        }
    }

    if(!checkSubseq(ans, A) || !checkSubseq(ans, B)) return vi{-1};

    return ans;
}

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