結果
問題 | No.489 株に挑戦 |
ユーザー |
👑 |
提出日時 | 2023-01-22 16:35:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 78 ms / 1,000 ms |
コード長 | 2,436 bytes |
コンパイル時間 | 1,038 ms |
コンパイル使用メモリ | 80,552 KB |
最終ジャッジ日時 | 2025-02-10 06:22:16 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <vector>using namespace std;template< typename T, typename F>struct SegmentTree{private:int n;vector<T> node;F f;T initer;public:SegmentTree(int n_, F f, T initer) : f(f),initer(initer) {n = 1;while(n < n_)n*=2;node.resize(2*n-1, initer);}SegmentTree(vector<T> x, F f, T initer) : f(f),initer(initer) {n = 1;while(n < x.size())n*=2;node.resize(2*n-1, initer);set(x);}void set(vector<T> x){for(int i = 0; n > i; i++){update(i,x[i]);}}void update(int x, T val){x += (n-1);node[x] = val;while(x > 0){x = (x-1)/2;node[x] = f(node[2*x+1],node[2*x+2]);}}void add(int x, T val){x += (n-1);node[x] += val;while(x > 0){x = (x-1)/2;node[x] = f(node[2*x+1],node[2*x+2]);}}T getf(int a,int b, int k=0, int l=0, int r=-1){if(r < 0){r = n-1;}if(r < a || b < l){return initer;}if(a <= l && r <= b){return node[k];}T vl = getf(a,b,2*k+1,l,(l+r)/2);T vr = getf(a,b,2*k+2,(l+r)/2+1,r);return f(vl,vr);}T operator[](int x){x += (n-1);return node[x];}};template <typename T, typename F>SegmentTree<T, F> get_segment_tree(int N, const F &f, T initer){return SegmentTree<T,F>{N,f,initer};}template <typename T, typename F>SegmentTree<T, F> get_segment_tree(vector<T> x, const F &f, T initer){return SegmentTree<T,F>{x,f, initer};}int main(){long long n,d,k;cin>>n>>d>>k;vector<pair<long long,int>> A(n);for(int i = 0; n > i; i++){cin>>A[i].first;A[i].second = i;}auto seg = get_segment_tree(A,[](pair<long long,int> a, pair<long long,int> b){if(a.first == b.first){if(a.second < b.second)return a;else return b;}else{if(a.first < b.first)return a;else return b;}}, {1000000000,-1});long long ans = 0;pair<int,int> ansi = {0,0};for(int i = 1; n > i; i++){auto x = seg.getf(max(0LL,i-d),i-1);if(ans < A[i].first-x.first){ans = A[i].first-x.first;ansi = make_pair(x.second, A[i].second);}}cout << ans*k << endl;if(ans)cout << ansi.first << " " << ansi.second << endl;}