Submission #43426429 - AtCoder Regular Contest 164

Contest Duration: 2023-07-09 21:00:00+0900 - 2023-07-09 23:00:00+0900 (local time) (120 minutes) Back to Home

Submission #43426429

Source Code Expand

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
const int M=998244353;
inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
inline int Mod(re int x){return x>=M?x-M:x;}
inline int ksm(re int x,re int y){
	re int s=1;
	while(y){
		if(y&1)s=1ll*s*x%M;
		x=1ll*x*x%M,y>>=1;
	}
	return s;
}
int t,n,m,a[1000002],ans,A[1000002],B[1000002],R[1000002],stk[1000002],tp,k,f[1000002],g[4004][4002];
char s[1000002];
int main(){
	n=read(),m=read();
	for(re int i=1;i<=m;++i)A[i]=read(),B[i]=read(),R[i]=A[i],R[i+m]=B[i]+1;
	k=m+m,R[++k]=1,R[++k]=n+1;
	sort(R+1,R+k+1),k=unique(R+1,R+k+1)-R-1;
	if(k==2){
		printf("0 %d\n",m);
		return 0;
	}
	for(re int i=1;i<k-1;++i)for(re int j=1;j<=m;++j)if(((A[j]<=R[i]&&B[j]>=R[i+1]-1)||(A[j]<=R[i+1]&&B[j]>=R[i+2]-1))&&((!(A[j]<=R[i]&&B[j]>=R[i+2]-1))))f[i]+=2;
	memset(g,0x3f,sizeof(g)),g[1][0]=0;
	for(re int i=1;i<k;++i)
		for(re int j=0;j<=i;++j)
			g[i+1][j]=min(g[i+1][j],g[i][j]),
			g[i+2][j+1]=min(g[i+2][j+1],g[i][j]+f[i]);
	re int d=1,c=0;
	while(d<k-1)d<<=1,++c;
	printf("%d %d",c,g[k][(k-1)-(d>>1)]);
}

Submission Info

Submission Time	2023-07-09 21:49:16+0900
Task	E - Segment-Tree Optimization
User	gyh20
Language	C++ (GCC 9.2.1)
Score	700
Code Size	1247 Byte
Status	AC
Exec Time	1281 ms
Memory	67912 KiB

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:5:9: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
    5 |  re int t=0;re char v=getchar();
      |         ^
./Main.cpp:5:21: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
    5 |  re int t=0;re char v=getchar();
      |                     ^
./Main.cpp: At global scope:
./Main.cpp:11:25: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   11 | inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
      |                         ^
./Main.cpp:11:34: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   11 | inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
      |                                  ^
./Main.cpp:12:23: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   12 | inline int Mod(re int x){return x>=M?x-M:x;}
      |                       ^
./Main.cpp:13:23: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   13 | inline int ksm(re int x,re int y){
      |                       ^
./Main.cpp:13:32: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   13 | inline int ksm(re int x,re int y){
      |                                ^
./Main.cpp: In function ‘int ksm(int, int)’:
./Main.cpp:14:9: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   14 |  re int s=1;
      |         ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:25:13: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   25 |  for(re int i=1;i<=m;++i)A[i]=read(),B[i]=read(),R[i]=A[i],R[i+m]=B[i]+1;
      |             ^
./Main.cpp:32:13: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   32 |  for(re int i=1;i<k-1;++i)for(re int j=1;j<=m;++j)if(((A[j]<=R[i]&&B[j]>=R[i+1]-1)||(A[j]<=R[i+1]&&B[j]>=R[i+2]-1))&&((!(A...

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

700 / 700

Status

× 2

× 53

Set Name	Test Cases
Sample	sample-01.txt, sample-02.txt
All	in-01.txt, in-02.txt, in-03.txt, in-04.txt, in-05.txt, in-06.txt, in-07.txt, in-08.txt, in-09.txt, in-10.txt, in-11.txt, in-12.txt, in-13.txt, in-14.txt, in-15.txt, in-16.txt, in-17.txt, in-18.txt, in-19.txt, in-20.txt, in-21.txt, in-22.txt, in-23.txt, in-24.txt, in-25.txt, in-26.txt, in-27.txt, in-28.txt, in-29.txt, in-30.txt, in-31.txt, in-32.txt, in-33.txt, in-34.txt, in-35.txt, in-36.txt, in-37.txt, in-38.txt, in-39.txt, in-40.txt, in-41.txt, in-42.txt, in-43.txt, in-44.txt, in-45.txt, in-46.txt, in-47.txt, in-48.txt, in-49.txt, in-50.txt, in-51.txt, sample-01.txt, sample-02.txt

Case Name	Status	Exec Time	Memory
in-01.txt	AC	581 ms	67728 KiB
in-02.txt	AC	14 ms	5228 KiB
in-03.txt	AC	985 ms	67660 KiB
in-04.txt	AC	986 ms	67600 KiB
in-05.txt	AC	981 ms	67664 KiB
in-06.txt	AC	291 ms	67696 KiB
in-07.txt	AC	176 ms	67596 KiB
in-08.txt	AC	291 ms	67788 KiB
in-09.txt	AC	299 ms	67700 KiB
in-10.txt	AC	527 ms	67764 KiB
in-11.txt	AC	292 ms	67904 KiB
in-12.txt	AC	297 ms	67796 KiB
in-13.txt	AC	116 ms	67652 KiB
in-14.txt	AC	176 ms	67724 KiB
in-15.txt	AC	118 ms	67780 KiB
in-16.txt	AC	288 ms	67832 KiB
in-17.txt	AC	523 ms	67836 KiB
in-18.txt	AC	521 ms	67600 KiB
in-19.txt	AC	83 ms	67596 KiB
in-20.txt	AC	174 ms	67656 KiB
in-21.txt	AC	86 ms	67820 KiB
in-22.txt	AC	87 ms	67880 KiB
in-23.txt	AC	289 ms	67760 KiB
in-24.txt	AC	249 ms	67788 KiB
in-25.txt	AC	89 ms	67756 KiB
in-26.txt	AC	270 ms	67840 KiB
in-27.txt	AC	268 ms	67608 KiB
in-28.txt	AC	895 ms	67888 KiB
in-29.txt	AC	319 ms	67604 KiB
in-30.txt	AC	323 ms	67836 KiB
in-31.txt	AC	7 ms	4340 KiB
in-32.txt	AC	6 ms	4196 KiB
in-33.txt	AC	42 ms	66320 KiB
in-34.txt	AC	48 ms	66156 KiB
in-35.txt	AC	58 ms	67828 KiB
in-36.txt	AC	1140 ms	67448 KiB
in-37.txt	AC	1281 ms	67220 KiB
in-38.txt	AC	963 ms	67096 KiB
in-39.txt	AC	1026 ms	67764 KiB
in-40.txt	AC	930 ms	67692 KiB
in-41.txt	AC	56 ms	66352 KiB
in-42.txt	AC	50 ms	66228 KiB
in-43.txt	AC	51 ms	66176 KiB
in-44.txt	AC	51 ms	66184 KiB
in-45.txt	AC	53 ms	66120 KiB
in-46.txt	AC	49 ms	66132 KiB
in-47.txt	AC	49 ms	66156 KiB
in-48.txt	AC	46 ms	66156 KiB
in-49.txt	AC	45 ms	66224 KiB
in-50.txt	AC	48 ms	66340 KiB
in-51.txt	AC	55 ms	67912 KiB
sample-01.txt	AC	45 ms	66132 KiB
sample-02.txt	AC	48 ms	66028 KiB