結果
問題 | No.1496 不思議な数え上げ |
ユーザー |
![]() |
提出日時 | 2021-04-30 23:05:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 569 ms / 3,000 ms |
コード長 | 1,272 bytes |
コンパイル時間 | 1,789 ms |
コンパイル使用メモリ | 176,980 KB |
実行使用メモリ | 18,816 KB |
最終ジャッジ日時 | 2024-07-19 02:53:58 |
合計ジャッジ時間 | 23,067 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N; cin >> N; vector<int> P(N); for (int i = 0; i < N; i++){ cin >> P[i]; } vector<long long> A(N); for (int i = 0; i < N; i++){ cin >> A[i]; } vector<long long> S(N + 1); S[0] = 0; for (int i = 0; i < N; i++){ S[i + 1] = S[i] + P[i]; } vector<int> p(N); for (int i = 0; i < N; i++){ p[P[i] - 1] = i; } set<int> st; st.insert(-1); st.insert(N); vector<int> L(N), R(N); for (int i = 0; i < N; i++){ auto itr1 = prev(st.lower_bound(p[i])); L[i] = *itr1 + 1; auto itr2 = st.lower_bound(p[i]); R[i] = *itr2; st.insert(p[i]); } for (int i = 0; i < N; i++){ int Lcnt = p[i] - L[i] + 1; int Rcnt = R[i] - p[i]; if (Lcnt <= Rcnt){ long long ans = 0; for (int j = L[i]; j <= p[i]; j++){ auto itr = upper_bound(S.begin() + p[i] + 1, S.begin() + R[i] + 1, A[i] + S[j]); ans += itr - (S.begin() + p[i] + 1); } cout << ans << endl; } else { long long ans = 0; for (int j = p[i] + 1; j <= R[i]; j++){ auto itr = lower_bound(S.begin() + L[i], S.begin() + p[i] + 1, S[j] - A[i]); ans += (S.begin() + p[i] + 1) - itr; } cout << ans << endl; } } }