結果
問題 | No.674 n連勤 |
ユーザー | 37zigen |
提出日時 | 2018-04-15 05:11:19 |
言語 | Fortran (gFortran 13.2.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 4,044 bytes |
コンパイル時間 | 360 ms |
コンパイル使用メモリ | 36,792 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 22:44:07 |
合計ジャッジ時間 | 1,605 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 5 ms
5,376 KB |
testcase_12 | AC | 5 ms
5,376 KB |
testcase_13 | AC | 30 ms
5,376 KB |
testcase_14 | AC | 40 ms
5,376 KB |
testcase_15 | AC | 44 ms
5,376 KB |
testcase_16 | AC | 50 ms
5,376 KB |
testcase_17 | AC | 51 ms
5,376 KB |
testcase_18 | AC | 45 ms
5,376 KB |
testcase_19 | AC | 47 ms
5,376 KB |
ソースコード
module algorithm_md contains recursive subroutine qsort(a,s,t) implicit none integer*8::a(:),m integer::s,t,i,j if(t-s<=1)return i=s j=t-1 m=a((s+t)/2) do do while(a(i)<m) i=i+1 end do do while(a(j)>m) j=j-1 end do if(i>=j)exit a(i)=xor(a(i),a(j)) a(j)=xor(a(i),a(j)) a(i)=xor(a(i),a(j)) i=i+1 j=j-1 end do call qsort(a,s,i) call qsort(a,j+1,t) end subroutine function binarysearch(a,v) integer*8::a(:),v integer::ok,ng,middle,binarysearch ok=1 ng=size(a)+1 do while(ng-ok>1) middle=(ok+ng)/2 if(a(middle)<=v)then ok=middle else ng=middle end if end do binarysearch=ok if(a(ok)/=v)then print*,"err" call exit(1) end if end function end module module djset_md private type,public::DJSet integer::n integer*8::ans=0 integer,allocatable::upper(:) integer*8,allocatable::mi(:),ma(:),top(:) contains procedure::build=>build_ procedure::root=>root_ procedure::setUnion=>setUnion_ procedure::equiv=>equiv_ procedure::confluentUnion=>confluentUnion_ end type contains subroutine build_(o,n_) implicit none integer::i,j,k class(DJSet)::o integer::n_ o%n=n_ allocate(o%upper(o%n)) allocate(o%ma(o%n)) allocate(o%mi(o%n)) allocate(o%top(o%n)) do i=1,o%n o%upper(i)=-1 o%top(i)=i end do end subroutine recursive function root_(o,x)result(res) implicit none class(DJSet)::o integer::x,res if(o%upper(x)<0)then res=x else o%upper(x)=o%root(o%upper(x)) res=o%upper(x) end if end function subroutine confluentUnion_(o,x,y) implicit none class(DJSet)::o integer::x,y,middle if(x>y)then x=xor(x,y) y=xor(x,y) x=xor(x,y) end if do while(.not.o%equiv(x,y)) !x<y middle=o%top(x)+1 call o%setUnion(x,middle) x=middle end do end subroutine subroutine setUnion_(o,x,y) implicit none class(DJSet)::o integer::x,y x=root_(o,x) y=root_(o,y) if(x==y)return if(o%upper(x)<o%upper(y))then x=xor(x,y) y=xor(x,y) x=xor(x,y) end if o%upper(y)=o%upper(x)+o%upper(y) o%upper(x)=y o%ma(y)=max(o%ma(x),o%ma(y)) o%mi(y)=min(o%mi(x),o%mi(y)) o%top(y)=max(o%top(x),o%top(y)) o%ans=max(o%ans,o%ma(y)-o%mi(y)) end subroutine function equiv_(o,x,y) implicit none class(DJSet)::o integer::x,y logical::equiv_ equiv_=o%root(x)==o%root(y) end function end module program main use algorithm_md use djset_md implicit none integer*8::D,Q integer::i,j,k integer*8,allocatable::a(:),b(:),tmp_arr(:) type(DJSet)::ds read(*,*)D,Q allocate(a(Q)) allocate(b(Q)) allocate(tmp_arr(2*Q)) do i=1,Q read(*,*)a(i),b(i) tmp_arr(i)=a(i) tmp_arr(i+Q)=b(i)+1 end do call qsort(tmp_arr,1,size(tmp_arr)+1) j=1 do i=1,size(tmp_arr) if(i+1<=size(tmp_arr).and.tmp_arr(i)==tmp_arr(i+1))cycle tmp_arr(j)=tmp_arr(i) j=j+1 end do tmp_arr=tmp_arr(1:j-1) call ds%build(j-1) do i=1,j-1 ds%ma(i)=tmp_arr(i) ds%mi(i)=tmp_arr(i) end do do i=1,Q call ds%confluentUnion(binarysearch(tmp_arr,a(i)),binarysearch(tmp_arr,b(i)+1)) print*,ds%ans end do end program