#631832 (C++17) No.1435 Mmm......

• 問題: No.1435 Mmm......
• ユーザー: 沙耶花
• 提出日時: 2021-03-19 22:31:43
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,518 ms / 2,000 ms
• コード長: 938 bytes
• コンパイル時間: 4,418 ms
• コンパイル使用メモリ: 266,904 KB
• 実行使用メモリ: 22,016 KB
• 最終ジャッジ日時: 2024-04-29 17:39:17
• 合計ジャッジ時間: 25,366 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	627 ms; 19,968 KB
testcase_07	AC	783 ms; 20,736 KB
testcase_08	AC	917 ms; 21,376 KB
testcase_09	AC	856 ms; 21,248 KB
testcase_10	AC	739 ms; 20,224 KB
testcase_11	AC	700 ms; 20,224 KB
testcase_12	AC	660 ms; 19,968 KB
testcase_13	AC	645 ms; 19,840 KB
testcase_14	AC	449 ms; 12,544 KB
testcase_15	AC	963 ms; 21,760 KB
testcase_16	AC	776 ms; 20,608 KB
testcase_17	AC	522 ms; 12,928 KB
testcase_18	AC	984 ms; 21,760 KB
testcase_19	AC	698 ms; 20,096 KB
testcase_20	AC	892 ms; 21,120 KB
testcase_21	AC	1,518 ms; 22,016 KB
testcase_22	AC	1,414 ms; 21,888 KB
testcase_23	AC	1,015 ms; 21,888 KB
testcase_24	AC	1,044 ms; 21,888 KB
testcase_25	AC	1,080 ms; 22,016 KB
testcase_26	AC	1,002 ms; 21,760 KB
testcase_27	AC	1,020 ms; 21,888 KB

ソースコード

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000000

struct Data{
	long long M=-Inf,m0 = Inf,m1 = Inf;
};

Data op(Data a,Data b){
	Data c;
	c.M = max(a.M,b.M);
	array<long long,4> A = {a.m0,a.m1,b.m0,b.m1};
	sort(A.begin(),A.end());
	c.m0 = A[0],c.m1 = A[1];
	return c;
	
}

Data e(){
	return Data();
}

int main(){
	
	int N;
	vector<long long> a;
	long long ans = 0LL;
	cin>>N;
	
	a.resize(N);
	vector<Data> D(N);
	rep(i,N){
		scanf("%lld",&a[i]);
		D[i] = Data();
		D[i].M = a[i];
		D[i].m0 = a[i];
	}
	
	segtree<Data,op,e> seg(D);
	
	rep(i,N-1){
		int ok = i+1,ng = N+1;
		while(ng-ok>1){
			int mid = (ok+ng)/2;
			auto ret = seg.prod(i,mid);
			if(ret.M <= ret.m0+ret.m1)ok = mid;
			else ng = mid;
		}
		ans += ok - (i+1);
	}
	
	cout<<ans<<endl;
	
	
	
    return 0;
}