Submission #982502

#	Time	Username	Problem	Language	Result	Execution time	Memory
982502		RandomUser	Grudanje (COCI19_grudanje)	C++17	70 / 70	242 ms	13840 KiB

grudanje

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

int main() {
    string s;
    cin >> s;

    int n = s.size(), q;
    cin >> q;
    s = "." + s;

    vector<int> L(q), R(q);
    for(int i=0; i<q; i++) cin >> L[i] >> R[i];

    vector<int> v(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];

    int l=0, r=n, ans=0;
    while(l <= r) {
        int mid = (l + r) / 2;
        int pref[26][n+1];
        memset(pref, 0, sizeof(pref));

        vector<bool> bad(n+1);
        for(int i=1; i<=mid; i++) bad[v[i]] = 1;

        for(int i=1; i<=n; i++) {
            for(int j=0; j<26; j++) pref[j][i] = pref[j][i-1];
            if(!bad[i]) pref[s[i]-'a'][i]++;
        }

        bool ok = 1;

        for(int i=0; i<q; i++)
            for(int j=0; j<26; j++)
                if(pref[j][R[i]] - pref[j][L[i]-1] > 1) ok = 0;

        if(ok) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    cout << ans << '\n';
    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