Submission #811169

#	Time	Username	Problem	Language	Result	Execution time	Memory
811169		Pring	Grudanje (COCI19_grudanje)	C++14	70 / 70	33 ms	4984 KiB

grudanje

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

#define int long long
typedef pair<int, int> pii;

const int MXN = 100005;
int n, q, a[MXN];
string s;
vector<pii> v, w;
set<int> S[26];

void DIST() {
    sort(w.begin(), w.end());
    for (int i = 0, j = 0; i < q; i = j) {
        while (j < q && w[i].first == w[j].first) j++;
        if (v.empty()) v.push_back(w[j - 1]);
        else if (w[j - 1].second > v.back().second) v.push_back(w[j - 1]);
    }
    q = v.size();
}

bool check(int x, int y) {
    // cout << "CHECK " << x << ' ' << y << endl;
    if (x < v[0].first) return true;
    int l = 0, r = q;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        (v[mid].first <= x ? l : r) = mid;
    }
    return !(y < v[l].second);
}

bool PUSH(int id) {
    int x = s[id] - 'a';
    auto it = S[x].insert(id).first;
    if (it != S[x].begin()) {
        auto it2 = --it;
        it++;
        if (!check(*it2, *it)) return true;
    }
    {
        auto it2 = ++it;
        it--;
        if (it2 != S[x].end()) {
            if (!check(*it, *it2)) return true;
        }
    }
    return false;
}

int solve() {
    cin >> s >> q;
    n = s.size();
    w.resize(q);
    for (auto &i : w) {
        cin >> i.first >> i.second;
        i.first--;
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    DIST();
    for (int i = n - 1; i > 0; i--) {
        if (PUSH(a[i])) return i + 1;
    }
    return 0;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cout << solve() << endl;
    return 0;
}

• 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