srednji.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <map>

using namespace std;

#define long long long

int n, key;

int a[1230997];

map<int, int> ma;

main(){

    int i, root;

    scanf("%d%d", &n, &key);

    for (i=1; i<=n; i++) scanf("%d", &a[i]);

    for (i=1; i<=n; i++){

        if (a[i]==key) { a[i]=0; root=i; }

        else if (a[i]<key) a[i]=-1;

        else a[i]=1;

    }

    int current_sum; long answer=0;

    current_sum=0;

    for (i=root; i>=1; i--){

        current_sum+=a[i];

        ma[current_sum]++;

    }

    current_sum=0;

    for (i=root; i<=n; i++){

        current_sum+=a[i];

        answer += ma[-current_sum];

    }

    printf("%lld\n", answer);

}

Nhận xét