結果
問題 | No.674 n連勤 |
ユーザー | ikd |
提出日時 | 2018-04-16 14:38:51 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 2,772 bytes |
コンパイル時間 | 1,724 ms |
コンパイル使用メモリ | 150,964 KB |
実行使用メモリ | 12,000 KB |
最終ジャッジ日時 | 2024-06-13 00:28:29 |
合計ジャッジ時間 | 3,247 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,944 KB |
testcase_06 | AC | 1 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,944 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 8 ms
6,940 KB |
testcase_12 | AC | 7 ms
6,944 KB |
testcase_13 | AC | 37 ms
6,944 KB |
testcase_14 | AC | 136 ms
11,788 KB |
testcase_15 | AC | 108 ms
10,624 KB |
testcase_16 | AC | 90 ms
11,336 KB |
testcase_17 | AC | 87 ms
12,000 KB |
testcase_18 | AC | 68 ms
11,140 KB |
testcase_19 | AC | 142 ms
11,288 KB |
ソースコード
void main(){ import std.stdio, std.string, std.conv, std.algorithm; long d; int q; rd(d, q); import std.typecons; alias Query=Tuple!(long, "a", long, "b"); auto queries=new Query[](q); long[] vals; foreach(i; 0..q){ long a, b; rd(a, b); queries[i]=Query(a, b+1); vals~=queries[i].a; vals~=queries[i].b; } sort(vals); int[long] map; foreach(val; vals){ if((val in map)==null) map[val]=map.length.to!(int); } long[int] rev; foreach(long k; map.keys){ rev[map[k]]=k; } // writeln(map); auto tree=new SquareRootDecompotision(map.length.to!(int)); long mx=0; foreach(query; queries){ int l=map[query.a], r=map[query.b]; tree.merge(l, r); long ol=rev[tree.getLeft(l)], or=rev[tree.getRight(l)]; mx=max(mx, or-ol); // writeln(ol, " ", or); writeln(mx); // tree.show; } } class SquareRootDecompotision{ int D=1; int[] st, ed; int[] buc_st, buc_ed; import std.algorithm; this(int n){ while(D*D<n) D++; st.length=ed.length=(D*D); buc_st.length=buc_ed.length=D; foreach(int i; 0..(D*D)) st[i]=ed[i]=i; fill(buc_st, -1); fill(buc_ed, -1); } void merge(int left, int right){ int l=min(left, st[left]), r=max(right, ed[right]); if(buc_st[left/D]>=0) chmin(l, buc_st[left/D]); if(buc_st[right/D]>=0) chmax(r, buc_ed[right/D]); if(left-1>=0){ if(st[left-1]<ed[left-1]) chmin(l, st[left-1]); if(buc_st[(left-1)/D]>=0) chmin(l, buc_st[(left-1)/D]); } int bl=l/D, br=r/D; if(br-bl<=1){ eachFill(l, r, l, r); }else{ eachFill(l, (bl+1)*D, l, r); buc_st[(bl+1)..br]=l; buc_ed[(bl+1)..br]=r; eachFill(br*D, r, l, r); } } void eachFill(int tl, int tr, int l, int r){ // j in [tl, tr) st[j]<-l, ed[j]<-r push(tl/D); push(tr/D); // import std.stdio; // writeln(tl, " ", tr, " ", l, " ", r); foreach(int j; tl..tr) st[j]=l, ed[j]=r; } void push(int k){ if(buc_st[k]>=0) st[k*D..(k+1)*D]=buc_st[k]; if(buc_ed[k]>=0) ed[k*D..(k+1)*D]=buc_ed[k]; buc_st[k]=buc_ed[k]=-1; } int getLeft(int i){ int l=i; if(buc_st[i/D]>=0){ l=min(l, buc_st[i/D]); }else{ l=min(l, st[i]); } return l; } int getRight(int i){ int r=i; if(buc_ed[i/D]>=0){ r=max(r, buc_ed[i/D]); }else{ r=max(r, ed[i]); } return r; } void show(){ import std.stdio; writeln(st); writeln(buc_st); writeln(ed); writeln(buc_ed); } } void chmin(T)(ref T l, T r){if(l>r)l=r;} void chmax(T)(ref T l, T r){if(l<r)l=r;} void rd(Type...)(ref Type x){ import std.stdio, std.string, std.conv; auto l=readln.split; assert(l.length==x.length); foreach(i, ref e; x){ e=l[i].to!(typeof(e)); } }