Submission #1272351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272351		flaming_top1	Grudanje (COCI19_grudanje)	C++20	70 / 70	78 ms	4256 KiB

grudanje

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;

using namespace std;

bool x[100005];
int n, q, bit[100005], idx[30], a[100005], pref[100005];
string s;
vector<int> Query[100005];

void upd(int idx, lint k)
{
    for (; idx <= n; idx += idx & -idx)
        bit[idx] += k;
}

lint get(int idx)
{
    lint res = 0;
    for (; idx; idx -= idx & -idx)
        res += bit[idx];

    return res;
}

lint query(int l, int r)
{
    return get(r) - get(l - 1);
}

bool check(lint mid)
{
    memset(bit, 0, sizeof bit);
    memset(x, 0, sizeof x);
    memset(pref, 0, sizeof pref);
    memset(idx, 0, sizeof idx);
    for (int i = 1; i <= mid; i++)
    {
        x[a[i]] = true;
        pref[a[i]] = 1;
    }
    for (int i = 1; i <= n; i++)
        pref[i] += pref[i - 1];

    for (int i = 1; i <= n; i++)
    {
        if (!x[i])
        {
            if (idx[s[i] - 'a'])
                upd(idx[s[i] - 'a'], -1);
            idx[s[i] - 'a'] = i;
            upd(i, 1);
        }
        for (auto l : Query[i])
        {
            if (query(l, i) == i - l + 1 - (pref[i] - pref[l - 1]))
                continue;
            else
                return false;
        }
    }
    return true;
}

lint binaryu()
{
    lint l = 0, r = n, mid, ans = -1;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return ans;
}

fami lore()
{
    SPED;
    cin >> s >> q;
    n = s.size();
    s = " " + s;
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        Query[r].emplace_back(l);
    }
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    cout << binaryu();
}
// Let your soul wander where dreams are born.

• 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