Submission #222367

#	Time	Username	Problem	Language	Result	Execution time	Memory
222367		tqbfjotld	Grudanje (COCI19_grudanje)	C++14	70 / 70	558 ms	13416 KiB

grudanje

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

int nextocc[100005];
vector<pair<int,int> > queries;
string str;
int pos[100005];
int q;
map<char,int> pre;

struct node{
int s,e,v;
node *l,*r;
node(int _s, int _e){
    s = _s;
    e = _e;
    v = 0;
    if (s!=e){
        l = new node(s,(s+e)/2);
        r = new node((s+e)/2+1,e);
    }
}
void refresh(){
    if (s==e){
        v = nextocc[s];
        return;
    }
    l->refresh();
    r->refresh();
    v = min(l->v,r->v);
}
int query(int a, int b){
    if (a<=s && e<=b){
        return v;
    }
    if (b<=(s+e)/2){
        return l->query(a,b);
    }
    if (a>(s+e)/2){
        return r->query(a,b);
    }
    return min(l->query(a,b),r->query(a,b));
}

}*root;

int main(){
cin>>str;
cin>>q;
for (int x = 0; x<q; x++){
    int a,b;
    cin>>a;
    cin>>b;
    a--;b--;
    queries.push_back({a,b});
}
for (int x = 0; x<str.size(); x++){
    int a;
    cin>>a;
    a--;
    pos[a] = x+1;
}
int n = str.size();
int l = -1;
int r = n;
root = new node(0,n);
while (l+1<r){
    int mid = (l+r)/2;
    for (int x = 0; x<n; x++){
        nextocc[x] = n+1;
    }
    pre.clear();
    for (int x = 0; x<n; x++){
        if (pos[x]<=mid){
            continue;
        }
        if (pre[str[x]]!=0){
            nextocc[pre[str[x]]-1] = x;
        }
        pre[str[x]] = x+1;
    }
    root->refresh();
    bool can = true;
    for (auto x : queries){
        if (root->query(x.first,x.second)<=x.second){
            can = false;
            break;
        }
    }
    if (can) r = mid;
    else l = mid;
}
printf("%d",r);

}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int x = 0; x<str.size(); x++){
                 ~^~~~~~~~~~~

• 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