제출 #1185453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185453		qrn	Grudanje (COCI19_grudanje)	C++20	70 / 70	276 ms	27256 KiB

grudanje

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

// #define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e9;
const intt mxN = 2e5 + 5;
const intt L = 21;

void solve() {
    string S;
    cin >> S;


    intt Q;
    cin >> Q;
    vector<pair<intt,intt>> qrys;
    for(intt i = 0; i < Q; i++) {
        intt a, b;
        cin >> a >> b;
        qrys.pb({a, b});
    }

    intt N = S.size();
    S = '#' + S;
    vector<intt> A(N);
    for(intt i = 0; i < N; i++) {
        cin >> A[i];
    }

    intt best = inf, l = 0, r = N;
    string temp = S;
    while(l <= r) {
        intt mid = (l + r) / 2;
        // cout << l << " " << mid << " " << r << " ";
        for(intt i = 1; i <= mid; i++){
            S[A[i-1]] = '*';
        }
        // cout << S << endl;

        vector<vector<intt>> cnt(N+1, vector<intt>(27, 0ll));
        for(intt i = 1; i <= N; i++) {
            for(intt j = 0; j < 26; j++) {
                cnt[i][j] += cnt[i-1][j];
                if(S[i] != '*' && (S[i] - 'a') == j) {
                    // if(j == 1) cout << "ZOR: " << i << " "; 
                    cnt[i][j]++;
                    // if(j == 1)
                    // cout << cnt[i][S[i]-'a'] << endl;
                }
            }
        }
        
        // for(intt i = 0; i < N; i++) {
        //     for(intt j = 0; j < 26; j++) {
        //         cout << cnt[i][j] << " ";
        //     }
        //     cout << endl;
        // }

        intt olur = 1;
        for(intt i = 0; i < Q; i++) {
            for(intt j = 0; j < 26; j++) {
                intt sag = cnt[qrys[i].se][j], sol = cnt[qrys[i].fi-1][j];
                
                // if(j == 0 || j == 1) {
                //     cout << sag << " " << sol << " :: " << qrys[i].fi << " " << qrys[i].se << endl;
                // }
                if(sag - sol <= 1) {
                    continue;
                } 
                olur = 0;
                break;
            }
            if(!olur) break;
        }

        if(!olur){
            l = mid + 1;
        } else {
            best = mid;
            r = mid - 1;
        }
        S = temp;
    }
    cout << best << endl;
}

signed main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

• 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