Submission #222378

#	Time	Username	Problem	Language	Result	Execution time	Memory
222378		cheeheng	Grudanje (COCI19_grudanje)	C++14	70 / 70	1133 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
    int lo = 0;
    int hi = N;
    while(lo < hi){
        int mid = (lo+hi)/2;
        if(boleh(mid)){
            hi = mid;
        }else{
            lo = mid+1;
        }
    }
    printf("%d", lo);
    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: 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