結果
問題 | No.1031 いたずら好きなお姉ちゃん |
ユーザー | IKyopro |
提出日時 | 2020-04-18 01:15:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,155 ms / 3,500 ms |
コード長 | 3,181 bytes |
コンパイル時間 | 2,585 ms |
コンパイル使用メモリ | 213,440 KB |
実行使用メモリ | 12,076 KB |
最終ジャッジ日時 | 2024-04-14 18:46:41 |
合計ジャッジ時間 | 51,849 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 2 ms
6,812 KB |
testcase_03 | AC | 38 ms
6,816 KB |
testcase_04 | AC | 38 ms
6,944 KB |
testcase_05 | AC | 38 ms
6,944 KB |
testcase_06 | AC | 38 ms
6,940 KB |
testcase_07 | AC | 38 ms
6,940 KB |
testcase_08 | AC | 38 ms
6,940 KB |
testcase_09 | AC | 38 ms
6,940 KB |
testcase_10 | AC | 39 ms
6,940 KB |
testcase_11 | AC | 940 ms
10,876 KB |
testcase_12 | AC | 928 ms
10,972 KB |
testcase_13 | AC | 1,151 ms
11,940 KB |
testcase_14 | AC | 980 ms
11,048 KB |
testcase_15 | AC | 1,084 ms
11,660 KB |
testcase_16 | AC | 923 ms
11,052 KB |
testcase_17 | AC | 1,074 ms
11,672 KB |
testcase_18 | AC | 1,037 ms
11,476 KB |
testcase_19 | AC | 1,090 ms
11,712 KB |
testcase_20 | AC | 1,145 ms
12,044 KB |
testcase_21 | AC | 1,035 ms
11,620 KB |
testcase_22 | AC | 922 ms
10,804 KB |
testcase_23 | AC | 949 ms
11,088 KB |
testcase_24 | AC | 1,098 ms
11,732 KB |
testcase_25 | AC | 1,123 ms
11,784 KB |
testcase_26 | AC | 1,049 ms
11,268 KB |
testcase_27 | AC | 983 ms
11,240 KB |
testcase_28 | AC | 1,155 ms
11,960 KB |
testcase_29 | AC | 1,148 ms
11,972 KB |
testcase_30 | AC | 1,153 ms
12,072 KB |
testcase_31 | AC | 1,150 ms
11,964 KB |
testcase_32 | AC | 1,150 ms
11,968 KB |
testcase_33 | AC | 1,155 ms
11,956 KB |
testcase_34 | AC | 1,146 ms
11,964 KB |
testcase_35 | AC | 1,124 ms
11,800 KB |
testcase_36 | AC | 1,121 ms
11,836 KB |
testcase_37 | AC | 1,124 ms
11,964 KB |
testcase_38 | AC | 1,098 ms
11,768 KB |
testcase_39 | AC | 1,063 ms
11,636 KB |
testcase_40 | AC | 1,089 ms
11,596 KB |
testcase_41 | AC | 1,097 ms
11,964 KB |
testcase_42 | AC | 1,089 ms
11,864 KB |
testcase_43 | AC | 1,079 ms
11,920 KB |
testcase_44 | AC | 1,064 ms
11,860 KB |
testcase_45 | AC | 1,025 ms
11,584 KB |
testcase_46 | AC | 1,096 ms
11,844 KB |
testcase_47 | AC | 1,099 ms
11,668 KB |
testcase_48 | AC | 1,140 ms
11,844 KB |
testcase_49 | AC | 1,127 ms
12,076 KB |
testcase_50 | AC | 1,106 ms
11,892 KB |
testcase_51 | AC | 1,147 ms
11,964 KB |
testcase_52 | AC | 1,152 ms
11,840 KB |
testcase_53 | AC | 1,154 ms
11,952 KB |
testcase_54 | AC | 2 ms
6,940 KB |
testcase_55 | AC | 1 ms
6,944 KB |
ソースコード
#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"; }