結果
問題 | No.2643 Many Range Sums Problems |
ユーザー |
|
提出日時 | 2024-02-20 16:22:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 118 ms / 8,000 ms |
コード長 | 1,813 bytes |
コンパイル時間 | 865 ms |
コンパイル使用メモリ | 79,104 KB |
最終ジャッジ日時 | 2025-02-19 18:09:15 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
#include<iostream> #include<algorithm> #include<vector> using namespace std; using ll=long long; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} const ll INF=1LL<<60; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; ll K; cin>>N>>K; vector<int>R(N); vector<ll>X(N); for(int i=0;i<N;i++){ cin>>R[i]>>X[i]; R[i]--; } for(int i=0;i<N;i++){ vector<ll>A(N),S(N+1); bool ok=true; for(int j=N-1;j>i;j--){ A[j]=X[j]-(S[j+1]-S[R[j]+1]); if(A[j]<0||A[j]>K){ ok=false; break; } S[j]=A[j]+S[j+1]; } if(!ok){ cout<<"No"<<"\n"; continue; } /* A[i] = x */ vector<ll>x(i+1),y(N+1); x[i]=1; y[i]=1; S[i]=S[i+1]; for(int j=i-1;j>=0;j--){ A[j]=X[j]-(S[j+1]-S[R[j]+1]); x[j]=-(y[j+1]-y[R[j]+1]); if(x[j]==0&&(A[j]<0||A[j]>K)){ ok=false; break; } S[j]=A[j]+S[j+1]; y[j]=x[j]+y[j+1]; } if(!ok){ cout<<"No"<<"\n"; }else{ ll l=-INF,r=INF; for(int j=i;j>=0;j--){ if(x[j]==1){ chmax(l,-A[j]); chmin(r,K-A[j]); }else if(x[j]==-1){ chmax(l,A[j]-K); chmin(r,A[j]); } } if(l>r)cout<<"No"<<"\n"; else cout<<"Yes"<<"\n"; } } }