結果
問題 | No.1435 Mmm...... |
ユーザー | 沙耶花 |
提出日時 | 2021-03-19 22:31:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,910 ms / 2,000 ms |
コード長 | 938 bytes |
コンパイル時間 | 6,082 ms |
コンパイル使用メモリ | 254,648 KB |
最終ジャッジ日時 | 2025-01-19 18:51:00 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:38:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | scanf("%lld",&a[i]); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#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 1000000000000struct 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;}