結果
問題 | No.2458 Line Up Charged Balls |
ユーザー |
👑 ![]() |
提出日時 | 2023-09-02 01:03:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 206 ms / 2,000 ms |
コード長 | 1,942 bytes |
コンパイル時間 | 1,057 ms |
コンパイル使用メモリ | 82,764 KB |
最終ジャッジ日時 | 2025-02-16 17:53:32 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <algorithm>#include <atcoder/modint>using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;using Modint = atcoder::static_modint<998244353>;struct LiCiaoTree {int N = 0;i64 off = 0;vector<i64> P;vector<i64> mid;vector<pair<i64, i64>> A;LiCiaoTree(int L, int R){N = 1; while(N < R-L+1) N *= 2;P.resize(N, R);mid.resize(N*2);rep(i,R-L+1) P[i] = L+i;for(int d=0; (1<<d)<N; d++){int q = N >> d;rep(i,1<<d) mid[(1<<d)+i] = P[q*i + q/2];}rep(i,N) mid[N+i] = P[i];A.assign(N*2, {0,-INF});off = L;}i64 maxval(i64 x){i64 pos = N + x - off;i64 ans = -INF;while(pos >= 1){ans = max(ans, A[pos].first * x + A[pos].second);pos /= 2;}return ans;}void update(i64 a, i64 b){i64 i = 1;pair<i64, i64> f = {a,b};while(true){if(A[i].first * mid[i] + A[i].second < f.first * mid[i] + f.second){swap(A[i], f);}if(i >= N) break;bool rightup = f.first - A[i].first > 0;i = i * 2 + (rightup ? 1 : 0);}}};int main(){int N; cin >> N;vector<i64> Q(N); rep(i,N) cin >> Q[i];auto ds = LiCiaoTree(-110000, 110000);i64 ans = -INF;rep(i,N){i64 prevmax = ds.maxval(Q[i]);ans = max(ans, prevmax);if(prevmax < 0) prevmax = 0;ds.update(Q[i], prevmax);}cout << ans << endl;return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;