結果
問題 | No.2698 Many Asakatsu |
ユーザー |
|
提出日時 | 2024-03-16 04:54:09 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 186 ms / 2,000 ms |
コード長 | 1,737 bytes |
コンパイル時間 | 2,973 ms |
コンパイル使用メモリ | 228,960 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 05:57:43 |
合計ジャッジ時間 | 6,418 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
コンパイルメッセージ
main.cpp: In function 'll f_i(int, ll)': main.cpp:27:8: warning: 'p' may be used uninitialized [-Wmaybe-uninitialized] 27 | ll p; | ^ main.cpp: In function 'bool CH(int, int, int)': main.cpp:27:8: warning: 'p' may be used uninitialized [-Wmaybe-uninitialized] main.cpp: In function 'int main()': main.cpp:27:8: warning: 'p' may be used uninitialized [-Wmaybe-uninitialized]
ソースコード
/*O(Nlog(D)+Q)*/#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>using namespace std;using ll=long long;using vll=vector<ll>;using vvll=vector<vll>;vll kousa,syoko;int N,M,Q;ll X;//D[i][0]+D[i][1]+...+D[i][p-1]ll SumD(ll i,ll p){if(p==0)return 0;return syoko[i]*p+p*(p-1)/2*kousa[i];}//f_i(x) O(1)ll f_i(int i,ll x){ll p;if(x<=syoko[i])p=0;else if(x>syoko[i]+kousa[i]*(M-1))p=M;else if(kousa[i]!=0)p=(x-syoko[i]-1)/kousa[i]+1;ll res=(SumD(i,M)-SumD(i,p))-SumD(i,p)+p*x-(M-p)*x;return res;}//O(logD)bool CH(int i,int j,int k){ll L=-1,R=1e9+1;while(R-L>1){ll M=(L+R)/2;if(f_i(j,M)<=f_i(k,M)){L=M;}else R=M;}return f_i(i,R-1)<=f_i(j,R-1);//不要}struct VCHT {void add(int a) {while (linesid.size()>=2&&CH(*(linesid.end() - 2), linesid.back(), a)) {linesid.pop_back();}linesid.push_back(a);}ll get(ll x) {while (linesid.size() >= 2 && f_i(linesid.front(),x) > f_i(linesid[1],x)) {linesid.pop_front();}return linesid.front();}deque<int> linesid;};int main(){cin.tie(nullptr);ios::sync_with_stdio(false);cin>>N>>M;kousa.resize(N);syoko.resize(N);for(int i=0;i<N;i++)cin>>syoko[i]>>kousa[i];VCHT V;for(int i=0;i<N;i++){V.add(i);}cin>>Q>>X;vll C(N);for(int i=0;i<N;i++)cin>>C[i];vector<int> AN(Q);for(int q=0;q<Q;q++){AN[q]=V.get(X);X+=C[AN[q]];if(X>1e9+5)X=1e9+5;}for(int q=0;q<Q;q++)cout<<AN[q]+1<<" \n"[q==Q-1];}