Submission #222376

#	Time	Username	Problem	Language	Result	Execution time	Memory
222376		dwsc	Grudanje (COCI19_grudanje)	C++14	70 / 70	792 ms	11768 KiB

grudanje

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int prevArr[100010];
struct node{
    int s,e,m,v;
    node *l,*r;
    node(int _s,int _e){
        s = _s;
        e = _e;
        m = (s+e)/2;
        v = 0;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void updateAll(){
        if (s == e) v = prevArr[s];
        else{
            l->updateAll();
            r->updateAll();
            v = max(l->v,r->v);
        }
    }
    int rmq(int x,int y){
        if(s == x && e == y) return v;
        if (y <= m) return l->rmq(x,y);
        if (x > m) return r->rmq(x,y);
        return max(l->rmq(x,m),r->rmq(m+1,y));
    }
}*root;
int main(){
    string s;
    cin >> s;
    int n,q;
    cin >> q;
    n = s.length();
    root = new node(0,n-1);
    ii arr[q];
    for (int i = 0; i < q; i++) {
        cin >> arr[i].first>> arr[i].second;
        arr[i].first--;
        arr[i].second--;
    }
    int toss[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> toss[i];
        toss[i]--;
    }
    int l = 0,r = n+1;
    while (l != r){
        int m = (l+r)/2;
        //cout << m << "here\n";
        char temp[n];
        for (int i  =0; i < n; i++) temp[i] = s[i];
        for (int i = 1; i <= m; i++) temp[toss[i]] = '-';
        int pos[26];
        for (int i = 0; i < 26; i++) pos[i] = -1;
        for (int i = 0; i < n; i++){
            if (temp[i] == '-') prevArr[i] = -1;
            else{
                prevArr[i] = pos[temp[i]-97];
                pos[temp[i]-97] = i;
            }
            //cout << prevArr[i] << " ";
        }
        //cout << "\n";
        root->updateAll();
        int can = 1;
        for (int i = 0; i < q; i++){
            //cout << arr[i].first << " " << arr[i].second << "\n";
            //cout << root->rmq(arr[i].first,arr[i].second) << "hi\n";
            if (root->rmq(arr[i].first,arr[i].second) >= arr[i].first) can = 0;
        }
        if (can) r = m;
        else l = m+1;
    }
    cout << l;
}

• 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