結果
問題 | No.3059 Range Tournament |
ユーザー |
👑 ![]() |
提出日時 | 2025-03-14 22:26:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 960 ms / 4,000 ms |
コード長 | 5,616 bytes |
コンパイル時間 | 1,139 ms |
コンパイル使用メモリ | 98,128 KB |
実行使用メモリ | 66,892 KB |
最終ジャッジ日時 | 2025-03-14 22:26:47 |
合計ジャッジ時間 | 24,360 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include <iostream> #include <string> #include <vector> #include <algorithm> namespace nachia{ template< class S, S op(S l, S r) > struct Segtree { private: int N; std::vector<S> A; int xN; void mergev(int i){ if(i < N) A[i] = op(A[i*2], A[i*2+1]); } template<class E> int minLeft2(int r, E cmp, int a = 0, int b = 0, int i = -1) const { static S x; if(i == -1){ a=0; b=N; i=1; x=A[0]; } if(r <= a) return a; if(b <= r){ S nx = op(A[i], x); if(cmp(nx)){ x = nx; return a; } } if(b - a == 1) return b; int q = minLeft2(r, cmp, (a+b)/2, b, i*2+1); if(q > (a+b)/2) return q; return minLeft2(r, cmp, a, (a+b)/2, i*2); } template<class E> int maxRight2(int l, E cmp, int a = 0, int b = 0, int i = -1) const { static S x; if(i == -1){ a=0; b=N; i=1; x=A[0]; } if(b <= l) return b; if(l <= a){ S nx = op(x, A[i]); if(cmp(nx)){ x = nx; return b; } } if(b - a == 1) return a; int q = maxRight2(l, cmp, a, (a+b)/2, i*2); if(q < (a+b)/2) return q; return maxRight2(l, cmp, (a+b)/2, b, i*2+1); } public: Segtree() : N(0) {} Segtree(int n, S e) : xN(n) { N = 1; while (N < n) N *= 2; A.assign(N * 2, e); } Segtree(const std::vector<S>& a, S e) : Segtree(a.size(), e){ for(int i=0; i<(int)a.size(); i++) A[i + N] = a[i]; for(int i=N-1; i>=1; i--) mergev(i); } S getE() const { return A[0]; } void set(int p, S x){ p += N; A[p] = x; for(int d=1; (1<<d)<=N; d++) mergev(p>>d); } S get(int p) const { return A[N+p]; } S prod(int l, int r) const { l += N; r += N; S ql = A[0], qr = A[0]; while(l<r){ if(l&1) ql = op(ql, A[l++]); if(r&1) qr = op(A[--r], qr); l /= 2; r /= 2; } return op(ql, qr); } S allProd() const { return A[1]; } // bool cmp(S) template<class E> int minLeft(int r, E cmp) const { return minLeft2(r, cmp); } // bool cmp(S) template<class E> int maxRight(int l, E cmp) const { int x = maxRight2(l, cmp); return x > xN ? xN : x; } }; } // namespace nachia #include <functional> #include <utility> namespace nachia { template<class T, class Cmp = std::less<T>> struct PointSetRangeMin{ private: static T minop(T l, T r){ return std::min(l, r, Cmp()); } using Base = Segtree<T, minop>; Base base; Cmp cmpx; public: PointSetRangeMin() {} PointSetRangeMin(int len, T INF) : base(len, INF){} PointSetRangeMin(const std::vector<T>& init, T INF) : base(init, INF){} T min(int l, int r){ return base.prod(l, r); } T min(){ return base.allProd(); } void set(int pos, T val){ base.set(pos, val); } T getinf() const { return base.getE(); } void setinf(int pos){ set(pos, getinf()); } T get(int pos){ return base.get(pos); } void chmin(int pos, T val){ base.set(pos, minop(get(pos), val)); } int lBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return cmpx(val, x); }); } int uBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return !cmpx(x, val); }); } int lBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return cmpx(val, x); }); } int uBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return !cmpx(x, val); }); } template<class E> int minLeft(int r, E cmp){ return base.minLeft(r, cmp); } template<class E> int maxRight(int l, E cmp){ return base.maxRight(l, cmp); } int argmin(int l, int r){ auto v = this->min(l, r); if(!cmpx(v, getinf())) return -1; return lBoundRight(l, v); } }; } // namespace nachia using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<i64(n); i++) const i64 INF = 1001001001001001001; template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; void testcase(){ i64 N; cin >> N; i64 Z = 18; vector<i64> A(N); rep(i,N){ cin >> A[i]; A[i]--; } vector<vector<i64>> F(Z, vector<i64>(N*2)); i64 Q; cin >> Q; auto ds = nachia::PointSetRangeMin<i64, greater<i64>>(A, -1); vector<i64> res(N); rep(qi,Q){ i64 l,r; cin >> l >> r; l--; if(r-l <= 1) continue; res[max(A[l], A[l+1])]++; i64 p = l + 2, q = r; i64 b = 2, t = 0; while(p < q){ i64 f = p + (q - p) / b * b; F[t][p] += 1; F[t][f] -= 1; if(f == q){ p = p + b; res[max(ds.min(l, p), ds.min(q, r))] += 1; } else { q = f; res[max(ds.min(l, p), ds.min(q, r))] += 1; } t++; b *= 2; } } rep(t,Z){ rep(i,N-(2<<t)) F[t][i+(2<<t)] += F[t][i]; rep(a,N-(1<<t)) chmax(A[a], A[a+(1<<t)]); rep(a,N-(2<<t)+1) res[A[a]] += F[t][a]; } rep(i,N){ cout << res[i] << "\n"; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); rep(t,1) testcase(); return 0; }