結果
問題 |
No.1031 いたずら好きなお姉ちゃん
|
ユーザー |
![]() |
提出日時 | 2020-04-18 01:15:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,316 ms / 3,500 ms |
コード長 | 3,181 bytes |
コンパイル時間 | 2,565 ms |
コンパイル使用メモリ | 210,032 KB |
最終ジャッジ日時 | 2025-01-09 21:01:32 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class T, class U> using Pa = pair<T, U>; template <class T> using vec = vector<T>; template <class T> using vvec = vector<vec<T>>; template<typename Monoid,typename F> class SegmentTree{ private: int sz; vector<Monoid> seg; const F op; const Monoid e; public: SegmentTree(int n,const F op,const Monoid &e):op(op),e(e){ sz = 1; while(sz<=n) sz <<= 1; seg.assign(2*sz,e); } void set(int k, const Monoid &x){ seg[k+sz] = x; } void build(){ for(int i=sz-1;i>0;i--){ seg[i] = op(seg[2*i],seg[2*i+1]); } } void update(int k,const Monoid &x){ k += sz; seg[k] = x; while(k>>=1){ seg[k] = op(seg[2*k],seg[2*k+1]); } } Monoid query(int l,int r){ Monoid L = e,R = e; for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){ if(l&1) L = op(L,seg[l++]); if(r&1) R = op(seg[--r],R); } return op(L,R); } Monoid operator[](const int &k)const{ return seg[k+sz]; } }; template<class T> class Compress { map<T,int> idx; map<int,T> value; vec<T> cmp,v; public: int N; Compress(){} void add(T x){v.push_back(x);} void build(){ for(auto &x:v) cmp.push_back(x); sort(cmp.begin(),cmp.end()); cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end()); N = cmp.size(); for (int i=0;i<N;i++) idx[cmp[i]] = i; } int id(T val) {return idx[val];} T val(int id) {return cmp[id];} }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vec<int> P(N); for(int i=0;i<N;i++){ P[i]--; cin >> P[i]; } auto op = [&](ll a,ll b){return a+b;}; auto conquer = [&](vec<int>& A,vec<int>& B){ int N = A.size(),M = B.size(); Compress<int> cmp; for(auto x:A) cmp.add(x); for(auto x:B) cmp.add(x); cmp.add(-1); cmp.build(); int n = cmp.N; SegmentTree<ll,decltype(op)> seg(n,op,0); vec<int> ma(2,-1),mi(2,1e9); int r = 0; ll res = 0; for(int l=0;l<N;l++){ mi[0] = min(mi[0],A[l]); if(A[l]<ma[0]) continue; ma[0] = A[l]; while(r<M && B[r]<ma[0]){ if(mi[1]>B[r]){ mi[1] = B[r]; seg.update(cmp.id(B[r]),1); } r++; } // cerr << mi[1] << " " << mi[0] << "\n"; res += seg.query(cmp.id(mi[1]),cmp.id(mi[0])); } // cerr << res << "\n"; return res; }; auto devide = [&](auto&& self,int l,int r)->ll{ if(r-l<2) return 0; cerr << l << " " << r << "\n"; int m = (l+r)/2; ll res = self(self,l,m)+self(self,m,r); vec<int> L,R; for(int i=l;i<m;i++) L.push_back(P[i]); for(int i=m;i<r;i++) R.push_back(P[i]); reverse(L.begin(),L.end()); res += conquer(L,R)+conquer(R,L); return res; }; cout << devide(devide,0,N) << "\n"; }