結果
問題 | No.1031 いたずら好きなお姉ちゃん |
ユーザー | IKyopro |
提出日時 | 2020-04-18 11:49:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 619 ms / 3,500 ms |
コード長 | 3,058 bytes |
コンパイル時間 | 2,383 ms |
コンパイル使用メモリ | 212,760 KB |
実行使用メモリ | 12,092 KB |
最終ジャッジ日時 | 2024-04-14 20:40:24 |
合計ジャッジ時間 | 29,077 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 18 ms
6,940 KB |
testcase_04 | AC | 17 ms
6,940 KB |
testcase_05 | AC | 16 ms
6,944 KB |
testcase_06 | AC | 17 ms
6,940 KB |
testcase_07 | AC | 17 ms
6,944 KB |
testcase_08 | AC | 16 ms
6,940 KB |
testcase_09 | AC | 17 ms
6,940 KB |
testcase_10 | AC | 17 ms
6,940 KB |
testcase_11 | AC | 483 ms
10,940 KB |
testcase_12 | AC | 491 ms
10,716 KB |
testcase_13 | AC | 602 ms
12,072 KB |
testcase_14 | AC | 511 ms
11,168 KB |
testcase_15 | AC | 576 ms
11,640 KB |
testcase_16 | AC | 485 ms
10,984 KB |
testcase_17 | AC | 570 ms
11,664 KB |
testcase_18 | AC | 553 ms
11,476 KB |
testcase_19 | AC | 594 ms
11,720 KB |
testcase_20 | AC | 619 ms
11,948 KB |
testcase_21 | AC | 557 ms
11,492 KB |
testcase_22 | AC | 487 ms
10,936 KB |
testcase_23 | AC | 495 ms
10,836 KB |
testcase_24 | AC | 584 ms
11,604 KB |
testcase_25 | AC | 605 ms
11,780 KB |
testcase_26 | AC | 555 ms
11,400 KB |
testcase_27 | AC | 522 ms
11,240 KB |
testcase_28 | AC | 611 ms
11,964 KB |
testcase_29 | AC | 605 ms
11,976 KB |
testcase_30 | AC | 594 ms
12,092 KB |
testcase_31 | AC | 600 ms
11,964 KB |
testcase_32 | AC | 603 ms
11,968 KB |
testcase_33 | AC | 598 ms
11,852 KB |
testcase_34 | AC | 599 ms
12,068 KB |
testcase_35 | AC | 575 ms
11,960 KB |
testcase_36 | AC | 562 ms
11,964 KB |
testcase_37 | AC | 590 ms
11,960 KB |
testcase_38 | AC | 569 ms
11,896 KB |
testcase_39 | AC | 534 ms
11,768 KB |
testcase_40 | AC | 579 ms
11,852 KB |
testcase_41 | AC | 569 ms
12,008 KB |
testcase_42 | AC | 552 ms
11,864 KB |
testcase_43 | AC | 536 ms
11,920 KB |
testcase_44 | AC | 526 ms
11,732 KB |
testcase_45 | AC | 506 ms
11,708 KB |
testcase_46 | AC | 575 ms
11,844 KB |
testcase_47 | AC | 556 ms
11,672 KB |
testcase_48 | AC | 593 ms
11,716 KB |
testcase_49 | AC | 588 ms
11,908 KB |
testcase_50 | AC | 557 ms
11,632 KB |
testcase_51 | AC | 592 ms
12,092 KB |
testcase_52 | AC | 585 ms
12,092 KB |
testcase_53 | AC | 584 ms
11,836 KB |
testcase_54 | AC | 2 ms
6,944 KB |
testcase_55 | AC | 2 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++; } res += seg.query(cmp.id(mi[1]),cmp.id(mi[0])); } return res; }; auto devide = [&](auto&& self,int l,int r)->ll{ if(r-l<2) return 0; 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"; }