Submission #443119

#	Time	Username	Problem	Language	Result	Execution time	Memory
443119		Abrar_Al_Samit	Grudanje (COCI19_grudanje)	C++17	70 / 70	413 ms	3588 KiB

grudanje

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


#define debug(x) cerr << '[' << (#x) << "] = " << x << '\n';

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

void PlayGround() {
    string s; 
    cin >> s;
    int N = s.size();
    int Q; 
    cin >> Q;
    vector<pair<int,int>>range(Q);
    for(auto& it : range) {
        cin >> it.first >> it.second;
        --it.first, --it.second;
    }
    int blur[N];
    for(auto & it : blur) cin >> it, --it;

    auto perfect = [=] (string t) {
        vector<vector<int>>app(26, vector<int>());
        for(int i=0; i<N; ++i) {
            if(t[i]=='#') continue;
            int ch = t[i] - 'a';
            app[ch].push_back(i);
        }
        for(auto it : range) {
            for(int i=0; i<26; ++i) {
                auto it2 = lower_bound(app[i].begin(), app[i].end(), it.first);
                if(it2==app[i].end()) continue;
                ++it2;
                if(it2==app[i].end()) continue;
                if(*it2 <= it.second) return false;
            }
        }
        return true;
    };

    int l = 0, r = N;
    while(l+1 < r) {
        int mid = (l+r)>>1;
        string t = s;
        for(int i=0; i<mid; ++i) {
            t[blur[i]] = '#';
        }
        if(perfect(t)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    for(; l<=r; ++l) {
        string t = s;
        for(int i=0; i<l; ++i) {
            t[blur[i]] = '#';
        }
        if(perfect(t)) break;
    }
    cout << l << '\n';

    #ifndef ONLINE_JUDGE
        cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
} 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //#ifndef ONLINE_JUDGE
      //  freopen("input.txt", "r", stdin);
    //#endif
    PlayGround();

    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