結果
問題 | No.3059 Range Tournament |
ユーザー |
![]() |
提出日時 | 2024-07-07 18:06:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 855 ms / 4,000 ms |
コード長 | 1,909 bytes |
コンパイル時間 | 2,236 ms |
コンパイル使用メモリ | 207,584 KB |
最終ジャッジ日時 | 2025-03-16 14:48:50 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/segtree> using namespace std; int op(int a, int b){ return max(a, b); } int e(){ return -1; } #ifdef LOCAL #include <debug_print.hpp> #define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define OUT(...) (static_cast<void>(0)) #endif int main(){ int N; cin>>N; assert(1 <= N && N <= 200000); vector<int> P(N); set<int>pst; for(int i = 0; i < N; i++){ cin >> P[i]; assert(1 <= P[i] && P[i] <= N); pst.insert(P[i]); P[i]--; } assert(pst.size() == N); int Q; cin >> Q; assert(1 <= Q && Q <= 200000); vector<int> L(Q), R(Q); for(int i = 0; i < Q; i++){ cin >> L[i] >> R[i]; assert(1 <= L[i] && L[i] < R[i] && R[i] <= N); L[i]--; } atcoder::segtree<int, op, e> seg(P); const int LOG = 18; vector dp(LOG, vector(N, 0LL)); vector ans(N, 0LL); for(int i = 0; i < Q; i++){ int l = L[i]; int num = R[i] - L[i]; for(int j = 0; num > 1; j++){ int r = l + (1 << j) * (num - 1); if(num % 2 == 1){ dp[j + 1][l]++; l += 1 << (j + 1); num /= 2; ans[max(seg.prod(r, R[i]), seg.prod(L[i], l))]++; } else{ num /= 2; dp[j][r - (1 << j)]++; ans[max(seg.prod(r - (1 << j), R[i]), seg.prod(L[i], l))]++; } } } for(int i = LOG - 1; i >= 1; i--){ for(int j = 0; j < N; j++){ if(i + 1 < LOG){ dp[i][j] += dp[i + 1][j]; if(j >= (1 << i)) dp[i][j] += dp[i + 1][j - (1 << i)]; } if(dp[i][j] == 0)continue; ans[seg.prod(j, j + (1 << i))] += dp[i][j]; } } for(int i = 0; i < N; i++){ cout << ans[i] << '\n'; } }