Submission #222377

#	Time	Username	Problem	Language	Result	Execution time	Memory
222377		cheeheng	Grudanje (COCI19_grudanje)	C++14	14 / 70	2094 ms	12664 KiB

grudanje

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

char S[100005];

int ft[28][100005];
int N, Q;

int a[100005];
int b[100005];
int p[100005];

int prefixSum[28][100005];

int init(){
    memset(ft, 0, sizeof(ft));
}

int rsq(int i, int b){
    int sum = 0;
    while(b){
        sum += ft[i][b];
        b -= b&(-b);
    }
    return sum;
}

int rsq(int i, int a, int b){
    return rsq(i, b)-rsq(i, a-1);
}

void update(int i, int k, int v){
    while(k <= N){
        ft[i][k] += v;
        k += k&(-k);
    }
}

bool boleh(int k){
    init();

    for(int i = 0; i < N; i ++){
        update(S[i]-'a', i+1, 1);
    }

    for(int i = 0; i < k; i ++){
        update(S[p[i]-1]-'a', p[i], -1);
    }

    for(int i = 0; i < Q; i ++){
        for(int j = 0; j < 26; j ++){
            //printf("boleh(%d) %d %d %d: %d\n", k, j, a[i], b[i], rsq(j, a[i], b[i]));
            if(rsq(j, a[i], b[i]) > 1){
                return false;
            }
        }
    }

    return true;
}

int main(){
    scanf(" %s", S);
    N = strlen(S);
    scanf("%d", &Q);

    /*for(int i = 0; i < 26; i ++){
        prefixSum[i][0] = 0;
        for(int j = 1; j <= N; j ++){
            prefixSum[i][j] = prefixSum[i][j-1] + (S[j-1] == ('a'+i));
        }
    }*/

    for(int i = 0; i < Q; i ++){
        scanf("%d%d", &a[i], &b[i]);
    }

    for(int i = 0; i < N; i ++){
        scanf("%d", &p[i]);
    }

    // This part can be improved to binary search the answer
    for(int i = 0; i <= N; i ++){
        if(boleh(i)){
            printf("%d", i);
            return 0;
        }
    }

    return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'int init()':
grudanje.cpp:17:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
grudanje.cpp: In function 'int main()':
grudanje.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", S);
     ~~~~~^~~~~~~~~~
grudanje.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
grudanje.cpp:75: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:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 7
• Subtask 5: 0 / 7
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7