結果
問題 | No.1654 Binary Compression |
ユーザー | chocorusk |
提出日時 | 2021-08-08 10:49:02 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,139 ms / 2,000 ms |
コード長 | 3,229 bytes |
コンパイル時間 | 3,931 ms |
コンパイル使用メモリ | 195,140 KB |
実行使用メモリ | 72,124 KB |
最終ジャッジ日時 | 2024-04-22 03:29:45 |
合計ジャッジ時間 | 22,799 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 608 ms
71,968 KB |
testcase_11 | AC | 613 ms
71,792 KB |
testcase_12 | AC | 614 ms
71,768 KB |
testcase_13 | AC | 617 ms
71,912 KB |
testcase_14 | AC | 600 ms
71,776 KB |
testcase_15 | AC | 613 ms
71,944 KB |
testcase_16 | AC | 1,139 ms
71,864 KB |
testcase_17 | AC | 1,096 ms
71,868 KB |
testcase_18 | AC | 619 ms
71,972 KB |
testcase_19 | AC | 617 ms
72,000 KB |
testcase_20 | AC | 620 ms
71,956 KB |
testcase_21 | AC | 625 ms
72,072 KB |
testcase_22 | AC | 622 ms
71,856 KB |
testcase_23 | AC | 86 ms
71,888 KB |
testcase_24 | AC | 86 ms
71,992 KB |
testcase_25 | AC | 86 ms
71,796 KB |
testcase_26 | AC | 87 ms
71,996 KB |
testcase_27 | AC | 794 ms
71,856 KB |
testcase_28 | AC | 769 ms
72,124 KB |
testcase_29 | AC | 87 ms
71,800 KB |
testcase_30 | AC | 88 ms
71,900 KB |
testcase_31 | AC | 87 ms
71,960 KB |
testcase_32 | AC | 86 ms
72,036 KB |
testcase_33 | AC | 772 ms
71,996 KB |
testcase_34 | AC | 762 ms
71,844 KB |
testcase_35 | AC | 89 ms
72,060 KB |
testcase_36 | AC | 91 ms
71,756 KB |
testcase_37 | AC | 91 ms
71,992 KB |
testcase_38 | AC | 89 ms
71,996 KB |
testcase_39 | AC | 87 ms
71,900 KB |
testcase_40 | AC | 89 ms
71,872 KB |
testcase_41 | AC | 85 ms
71,848 KB |
testcase_42 | AC | 62 ms
7,312 KB |
testcase_43 | AC | 61 ms
7,308 KB |
testcase_44 | AC | 85 ms
71,928 KB |
testcase_45 | AC | 87 ms
71,932 KB |
testcase_46 | AC | 62 ms
7,440 KB |
testcase_47 | AC | 2 ms
5,376 KB |
testcase_48 | AC | 2 ms
5,376 KB |
testcase_49 | AC | 1,008 ms
71,992 KB |
testcase_50 | AC | 1,014 ms
71,928 KB |
testcase_51 | AC | 348 ms
71,892 KB |
testcase_52 | AC | 352 ms
72,000 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; template<typename Monoid, typename OperatorMonoid=Monoid> struct LazySegmentTree{ using F=function<Monoid(Monoid, Monoid)>; using G=function<Monoid(Monoid, OperatorMonoid, int)>; using H=function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>; int sz; vector<Monoid> data; vector<OperatorMonoid> lazy; const F f; const G g; const H h; const Monoid e1; const OperatorMonoid e0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &e1, const OperatorMonoid &e0): f(f), g(g), h(h), e1(e1), e0(e0){ sz=1; while(sz<n) sz<<=1; data.resize(2*sz-1, e1); lazy.resize(2*sz-1, e0); } void build(vector<Monoid> v){ for(int i=0; i<v.size(); i++) data[i+sz-1]=v[i]; for(int i=sz-2; i>=0; i--) data[i]=f(data[2*i+1], data[2*i+2]); } void eval(int k, int l, int r){ if(lazy[k]!=e0){ data[k]=g(data[k], lazy[k], r-l); if(k<sz-1){ lazy[2*k+1]=h(lazy[2*k+1], lazy[k]); lazy[2*k+2]=h(lazy[2*k+2], lazy[k]); } } lazy[k]=e0; } void update(int a, int b, const OperatorMonoid &x, int k, int l, int r){ eval(k, l, r); if(r<=a || b<=l) return; if(a<=l && r<=b){ lazy[k]=h(lazy[k], x); eval(k, l, r); }else{ update(a, b, x, 2*k+1, l, (l+r)/2); update(a, b, x, 2*k+2, (l+r)/2, r); data[k]=f(data[2*k+1], data[2*k+2]); } } void update(int a, int b, const OperatorMonoid &x){ return update(a, b, x, 0, 0, sz); } Monoid find(int a, int b, int k, int l, int r){ eval(k, l, r); if(b<=l || r<=a) return e1; if(a<=l && r<=b) return data[k]; else return f(find(a, b, 2*k+1, l, (l+r)/2), find(a, b, 2*k+2, (l+r)/2, r)); } Monoid find(int a, int b){ return find(a, b, 0, 0, sz); } Monoid operator[](const int &k){ return find(k, k+1); } }; using mint=static_modint<924844033>; int main() { string s; cin>>s; int n=s.size(); int l=0; while(l<n && s[l]=='0') l++; if(l==n){ cout<<n<<endl; return 0; } int r=n-1; while(r>=0 && s[r]=='0') r--; mint c=mint(l+1)*mint(n-r); s=s.substr(l, r-l+1); n=s.size(); auto f=[&](mint a, mint b){ return a+b; }; auto g=[&](mint a, mint x, int len){ return x*len; }; auto h=[&](mint x, mint y){ return y; }; LazySegmentTree<mint, mint> seg(n+1, f, g, h, 0, 0); int i=0; while(s[i]=='1') i++; mint v=1, tot=i; while(i<n){ int c0=0, c1=0; while(s[i]=='0') i++, c0++; while(s[i]=='1') i++, c1++; v+=(seg.find(0, c0)+tot*c0); seg.update(0, c0, -tot); tot+=v*c1; } mint ans=c*(seg[n]+tot); cout<<ans.val()<<endl; return 0; }