Submission #229227

#	Time	Username	Problem	Language	Result	Execution time	Memory
229227		VEGAnn	Grudanje (COCI19_grudanje)	C++14	70 / 70	131 ms	14020 KiB

grudanje

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
using namespace std;
const int N = 100100;
string s;
int n, p[N], l[N], r[N], sf[N][26], q; 
bool mrk[N];

bool ok(int x){
    fill(mrk, mrk + n, 0);
    
    for (int i = 0; i < x; i++)
        mrk[p[i]] = 1;
    
    fill(sf[n], sf[n] + 26, 0);
    
    for (int i = n - 1; i >= 0; i--){
        
        for (int j = 0; j < 26; j++)
            sf[i][j] = sf[i + 1][j];
        
        if (!mrk[i])
            sf[i][s[i] - 'a']++;
    }
    
    for (int i = 0; i < q; i++)
        for (int j = 0; j < 26; j++)
            if (sf[l[i]][j] - sf[r[i]][j] > 1)
                return 0;
    
    return 1;
}

int main(){

    ios_base::sync_with_stdio(0); cin.tie(0);
    
//    freopen("in.txt","r",stdin);
    
    cin >> s;
    n = sz(s);
    
    cin >> q;
    
    for (int i = 0; i < q; i++){
        cin >> l[i] >> r[i];
        l[i]--; 
    }
    
    for (int i = 0; i < n; i++){
        cin >> p[i];
        p[i]--;
    }
    
    int l1 = 0, r1 = n;
    
    while (l1 < r1){
        int md = (l1 + r1) >> 1;
        
        if (ok(md))
            r1 = md;
        else l1 = md + 1;
    }
    
    cout << l1;

    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