Submission #222380

#	Time	Username	Problem	Language	Result	Execution time	Memory
222380		dantoh000	Grudanje (COCI19_grudanje)	C++14	70 / 70	601 ms	52216 KiB

grudanje

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int a[100005], b[100005];
int c[100005];
int t[100005];
inline ii op(ii r, ii l){
    int l1 = l.first, r1 = r.first;
    int l2 = l.second, r2 = r.second;
    if (l1 > r1){
        return {l1,max(r1,l2)};
    }
    else{
        return {r1,max(r2,l1)};
    }
}
struct node{
    int s,e,m;
    ii v[26];
    node *l, *r;
    node (int _s, int _e){
        s = _s, e = _e, m = (s+e)/2;
        for (int i = 0; i < 26; i++) v[i] = {0,0};
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }
    void up(int id, int x, int nv){
        if (s == e){
            v[id].first = nv;
            return;
        }
        else if (x <= m){
            l->up(id,x,nv);
        }
        else r->up(id,x,nv);
        v[id] = op(l->v[id],r->v[id]);
    }
    ii query(int id, int qs, int qe){
        //printf("%d %d %d\n",id,qs,qe);
        if (qs == s && qe == e){
            return v[id];
        }
        if (qs > m) return r->query(id,qs,qe);
        else if (qe <= m) return l->query(id,qs,qe);
        else{
            ii L = l->query(id,qs,m);
            ii R = r->query(id,m+1,qe);
            ii ans = op(L,R);
            //printf("%d %d %d %d -> %d %d\n",L.first,L.second,R.first,R.second,ans.first,ans.second);
            return ans;
        }
    }
} *root;
int main(){
    string s;
    cin >> s;
    int n =s.size();
    root = new node(0,n-1);
    int q;
    scanf("%d",&q);
    for (int i = 0; i < q; i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    for (int i = 0; i < n; i++){
        scanf("%d",&c[i]);
        t[c[i]-1] = i+1;
    }
    for (int i = 0; i < n; i++){
        //printf("%d %d\n",s[i]-'a',t[i]);
        root->up(s[i]-'a',i,t[i]);
    }
    int ans = 0;
    for (int i = 0; i < q; i++){
        for (int k = 0; k < 26; k++){
            int res = root->query(k,a[i]-1,b[i]-1).second;
            //printf("(%d,%d) for char %d: %d\n",a[i],b[i],k,res);
            ans = max(ans,res);
        }
    }
    printf("%d",ans);
}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
grudanje.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a[i],&b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~
grudanje.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&c[i]);
         ~~~~~^~~~~~~~~~~~

• 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