結果

問題 No.956 Number of Unbalanced
コンテスト
ユーザー tarattata1
提出日時 2019-12-19 03:59:42
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
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