Submission #1214451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214451		Nelt	Hieroglyphs (IOI24_hieroglyphs)	C++20	18 / 100	1105 ms	1056820 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
struct SegTree
{
    ll n;
    vector<pair<ll, ll>> st;
    SegTree(ll sz = 0)
    {
        n = sz;
        st.resize(n << 1, make_pair(0, -1));
    }
    void build()
    {
        for (ll i = n - 1; i >= 1; i--)
            st[i] = max(st[i << 1], st[i << 1 | 1]);
    }
    void modify(ll p, pair<ll, ll> val)
    {
        for (st[p + n] = max(st[p + n], val), p += n; p > 1; p >>= 1)
            st[p >> 1] = max(st[p], st[p ^ 1]);
    }
    pair<ll, ll> query(ll l, ll r)
    {
        pair<ll, ll> ans = make_pair(0, -1);
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                ans = max(ans, st[l++]);
            if (r & 1)
                ans = max(ans, st[--r]);
        }
        return ans;
    }
};
std::vector<int> ucs(std::vector<int> a, std::vector<int> b)
{
    {
        set<ll> sa, sb;
        for (ll i : a)
            sa.insert(i);
        for (ll i : b)
            sb.insert(i);
        vector<int> nv;
        for (ll i : a)
            if (sb.count(i))
                nv.push_back(i);
        a = nv;
        nv.clear();
        for (ll i : b)
            if (sa.count(i))
                nv.push_back(i);
        b = nv;
    }
    vector<int> ans;
    set<ll> s;
    map<ll, vector<ll>> freqb;
    map<ll, ll> cnt;
    for (ll i : a)
        cnt[i]++;
    for (ll i = 0; i < b.size(); i++)
        freqb[b[i]].push_back(i);
    vector<ll> event[a.size() + 1];
    for (ll i = 0; i < a.size(); i++)
        if (cnt[a[i]] == 2)
        {
            if (s.count(a[i]))
                event[i].push_back(freqb[a[i]].back());
            else
                event[i + 1].push_back(freqb[a[i]].back()), s.insert(a[i]);
        }
    s.clear();
    for (ll i = 0; i < a.size(); i++)
    {
        for (ll j : event[i])
            if (s.count(j))
                s.erase(j);
            else
                s.insert(j);
        auto [l, r] = array<ll, 2>{freqb[a[i]].front(), freqb[a[i]].back()};
        auto it = s.upper_bound(l);
        if (it != s.end() and *it < r)
            return {-1};
    }
    vector<pair<ll, ll>> v;
    for (ll i = 0; i < a.size(); i++)
        for (ll j : freqb[a[i]])
            v.push_back(make_pair(i, j));
    SegTree st(v.size());
    pair<ll, ll> dp[v.size()];
    ll ptr = 0;
    for (ll i = 0; i < v.size(); i++)
    {
        auto [a, b] = v[i];
        while (ptr < i and v[ptr].first < a)
            st.modify(v[ptr].second, make_pair(dp[ptr].first, ptr)), ptr++;
        dp[i] = st.query(0, b - 1);
        dp[i].first++;
    }
    if (v.empty()) return {};
    ll best = max_element(dp, dp + v.size()) - dp;
    while (best + 1)
        ans.push_back(b[v[best].second]), best = dp[best].second;
    reverse(ans.begin(), ans.end());
    if (ans.size() != cnt.size()) return {-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