結果
問題 | No.956 Number of Unbalanced |
ユーザー | tarattata1 |
提出日時 | 2019-12-19 03:59:42 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 3,627 bytes |
コンパイル時間 | 1,333 ms |
コンパイル使用メモリ | 87,616 KB |
実行使用メモリ | 9,956 KB |
最終ジャッジ日時 | 2023-09-21 04:54:26 |
合計ジャッジ時間 | 3,495 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 39 ms
6,336 KB |
testcase_07 | AC | 45 ms
5,236 KB |
testcase_08 | AC | 36 ms
6,024 KB |
testcase_09 | AC | 23 ms
4,376 KB |
testcase_10 | AC | 31 ms
4,376 KB |
testcase_11 | AC | 55 ms
7,736 KB |
testcase_12 | AC | 39 ms
6,448 KB |
testcase_13 | AC | 13 ms
4,692 KB |
testcase_14 | AC | 92 ms
9,932 KB |
testcase_15 | AC | 18 ms
4,712 KB |
testcase_16 | AC | 47 ms
8,488 KB |
testcase_17 | AC | 16 ms
4,692 KB |
testcase_18 | AC | 78 ms
9,956 KB |
testcase_19 | AC | 18 ms
4,832 KB |
testcase_20 | AC | 83 ms
9,956 KB |
testcase_21 | AC | 14 ms
4,664 KB |
testcase_22 | AC | 17 ms
4,744 KB |
testcase_23 | AC | 45 ms
8,500 KB |
testcase_24 | AC | 18 ms
4,692 KB |
testcase_25 | AC | 27 ms
4,380 KB |
testcase_26 | AC | 17 ms
4,376 KB |
testcase_27 | AC | 25 ms
4,380 KB |
testcase_28 | AC | 28 ms
4,376 KB |
testcase_29 | AC | 78 ms
9,948 KB |
ソースコード
#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; }