結果

問題 No.956 Number of Unbalanced
ユーザー tarattata1tarattata1
提出日時 2019-12-19 03:59:42
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 96 ms / 2,000 ms
コード長 3,627 bytes
コンパイル時間 979 ms
コンパイル使用メモリ 84,068 KB
実行使用メモリ 10,112 KB
最終ジャッジ日時 2024-07-06 23:28:25
合計ジャッジ時間 3,079 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 42 ms
6,940 KB
testcase_07 AC 47 ms
6,940 KB
testcase_08 AC 38 ms
6,944 KB
testcase_09 AC 24 ms
6,944 KB
testcase_10 AC 31 ms
6,944 KB
testcase_11 AC 61 ms
7,808 KB
testcase_12 AC 42 ms
6,940 KB
testcase_13 AC 16 ms
6,940 KB
testcase_14 AC 94 ms
9,984 KB
testcase_15 AC 19 ms
6,944 KB
testcase_16 AC 48 ms
8,704 KB
testcase_17 AC 18 ms
6,940 KB
testcase_18 AC 96 ms
9,984 KB
testcase_19 AC 19 ms
6,940 KB
testcase_20 AC 96 ms
10,112 KB
testcase_21 AC 15 ms
6,944 KB
testcase_22 AC 18 ms
6,940 KB
testcase_23 AC 45 ms
8,576 KB
testcase_24 AC 20 ms
6,940 KB
testcase_25 AC 28 ms
6,940 KB
testcase_26 AC 17 ms
6,944 KB
testcase_27 AC 26 ms
6,944 KB
testcase_28 AC 28 ms
6,940 KB
testcase_29 AC 93 ms
9,856 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’:
main.cpp:145:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  145 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:150:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  150 |         scanf("%d", &tmp);
      |         ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;
using namespace std;

template<class T> class BIT   // 1-indexed (0 is not used)
{
private:
    int num;
    vector<T> bit;
public:
    BIT(int n):bit(vector<T>(n+1, 0)), num(n) {}

    T sum(int i) {   // sum of 1..i
        if (!i) return 0;
        return bit[i] + sum(i-(i&-i));
    }

    void add(int i, T x) {
        if (i > num) return;
        bit[i] += x;
        add(i+(i&-i), x);
    }

    int lower_bound(T x) {
        T res=0;
        int N=1;
        while(N<num) N*=2;
        int i;
        for(i=N/2; i>0; i/=2) {
            if(res+i<num && bit[res+i]<x) {
                x = x - bit[res +i];
                res = res + i;
            }
        }
        return res + 1;
    }
};

struct DATA {
    DATA(int _l, int _r, int _n0, int _n1)
        :l(_l),r(_r),n0(_n0),n1(_n1){};

    int l; int r; int n0; int n1;
};

bool merge( DATA prev, DATA& curr, int n, const vector<int>& v)
{
    if(v[prev.r]+prev.n1 < v[curr.l]-curr.n0) {
        return false;
    }
    int prev_num=prev.r-prev.l+1;
    int offset0=v[curr.l]-v[prev.l];
    int new_n0=MAX(prev.n0, curr.n0+prev_num-(offset0-prev_num));

    int curr_num=curr.r-curr.l+1;
    int offset1=v[curr.r]-v[prev.r];
    int new_n1=MAX(curr.n1, prev.n1+curr_num-(offset1-curr_num));

    curr=DATA(prev.l, curr.r, new_n0, new_n1);
    return true;
}

ll calc( DATA curr, int n, const vector<int>& v)
{
    int range[2]={MAX(0,v[curr.l]-curr.n0), MIN(n-1,v[curr.r]+curr.n1)};
    int N=range[1]-range[0]+1;
    vector<int> A(N,-1),S(N+1);
    int i;
    for(i=curr.l; i<=curr.r; i++) {
        A[v[i]-range[0]]=1;
    }
    for(i=0; i<N; i++) {
        S[i+1]=S[i]+A[i];
    }

    BIT<int> bit(N*2);
    ll ans=0;
    for(i=0; i<=N; i++) {
        int tmp=S[i]+N;
        ans+=bit.sum(tmp-1);
        bit.add(S[i]+N,1);
    }

    return ans;
}

ll func( int n, const vector<int>& v)
{
    int siz=(int)v.size();
    
    vector<DATA> z;    // vを複数個の区間(連続部分列)に分けたもの。
                       // (l,r,n0,n1)が、vのうち index l から index rまでを取り出した区間(部分列)を表す。
                       // n0,n1はそれぞれ左,右に何個のばした範囲まで考えるべきかを記録。

    // 範囲が干渉する区間をマージ
    int i;
    for(i=0; i<siz; i++) {
        DATA curr(i,i,1,1);
        while(!z.empty()) {
            DATA prev=z.back();
            if(merge(prev,curr, n,v)) {
                z.pop_back();
            }
            else {
                break;
            }
        }
        z.push_back(curr);
    }

    // 各区間について答を計算
    ll ans=0;
    int siz0=(int)z.size();
    for(i=0; i<siz0; i++) {
        ans+=calc(z[i], n, v);
    }

    return ans;
}

int main(int argc, char* argv[])
{
    int n;
    scanf("%d", &n);
    map<int, vector<int> > z;
    int i;
    for(i=0; i<n; i++) {
        int tmp;
        scanf("%d", &tmp);
        z[tmp].push_back(i);
    }

    ll ans=0;
    auto it=z.begin();
    for(; it!=z.end(); ++it) {
        ans+=func(n, it->second);
    }
    printf("%lld\n", ans);

    return 0;
}
0