Submission #66306

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
66306	2018-08-10T07:54:54 Z	정원준(#1889)	초음속철도 (OJUZ11_rail)	C++11	0 / 100	174 ms	10112 KB

rail

#include <bits/stdc++.h>
#define L long long
#define mod 1000000007


using namespace std;

L ln,n,ans;

struct S{
	L s,e;
}a[200020];

bool operator<(S a,S b){
	return a.e<b.e;
}

L dp[200020][2],ds[200020][2];


int main()
{
	scanf("%lld %lld",&ln,&n);
	L i;
	for(i=1;i<=n;i++)
	{
		scanf("%lld %lld",&a[i].s,&a[i].e);
	}
	sort(a+1,a+n+1);
	dp[0][1]=1;
	ds[0][1]=1;
	a[0].s=a[0].e=1;
	for(i=1;i<=n;i++)
	{
		L S=0,E=i;//Ŀ���Ǳ� �����ϴ� ��
		while(S<E)
		{
			L mid=(S+E)/2;
			if(a[mid].e>=a[i].s) E=mid;
			else S=mid+1;
		} 
		if(a[i].s==1)
		{
			dp[i][1]=ds[i-1][0]+ds[i-1][1];
			dp[i][0]=0;
		}
		else
		{
			dp[i][1]=ds[i-1][1]-ds[S-1][1];
			dp[i][0]=ds[i-1][0]-ds[S-1][0]+1;
		}
		dp[i][1]=(dp[i][1]%mod+mod)%mod;
		dp[i][0]=(dp[i][0]%mod+mod)%mod;
		ds[i][1]=ds[i-1][1]+dp[i][1];
		ds[i][0]=ds[i-1][0]+dp[i][0];
		ds[i][1]=(ds[i][1]%mod+mod)%mod;
		ds[i][0]=(ds[i][0]%mod+mod)%mod;
		//printf("%lld %lld : %lld , %lld %lld\n",a[i].s,a[i].e,S,dp[i][0],dp[i][1]);
	}
	for(i=1;i<=n;i++)
	{
		if(a[i].e==ln)
		{
			ans+=dp[i][1];
			ans%=mod;
		}
	}
	printf("%lld ",ans);
}

Compilation message

rail.cpp: In function 'int main()':
rail.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&ln,&n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
rail.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&a[i].s,&a[i].e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Incorrect	2 ms	432 KB	Output isn't correct
4	Incorrect	2 ms	564 KB	Output isn't correct
5	Correct	2 ms	564 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Incorrect	3 ms	564 KB	Output isn't correct
8	Incorrect	2 ms	572 KB	Output isn't correct
9	Correct	2 ms	736 KB	Output is correct
10	Incorrect	2 ms	736 KB	Output isn't correct
11	Correct	2 ms	736 KB	Output is correct
12	Incorrect	3 ms	736 KB	Output isn't correct
13	Correct	2 ms	736 KB	Output is correct
14	Correct	2 ms	736 KB	Output is correct
15	Incorrect	2 ms	736 KB	Output isn't correct
16	Incorrect	3 ms	736 KB	Output isn't correct
17	Correct	2 ms	736 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Incorrect	2 ms	432 KB	Output isn't correct
4	Incorrect	2 ms	564 KB	Output isn't correct
5	Correct	2 ms	564 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Incorrect	3 ms	564 KB	Output isn't correct
8	Incorrect	2 ms	572 KB	Output isn't correct
9	Correct	2 ms	736 KB	Output is correct
10	Incorrect	2 ms	736 KB	Output isn't correct
11	Correct	2 ms	736 KB	Output is correct
12	Incorrect	3 ms	736 KB	Output isn't correct
13	Correct	2 ms	736 KB	Output is correct
14	Correct	2 ms	736 KB	Output is correct
15	Incorrect	2 ms	736 KB	Output isn't correct
16	Incorrect	3 ms	736 KB	Output isn't correct
17	Correct	2 ms	736 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Incorrect	2 ms	748 KB	Output isn't correct
20	Incorrect	3 ms	748 KB	Output isn't correct
21	Correct	2 ms	748 KB	Output is correct
22	Incorrect	2 ms	748 KB	Output isn't correct
23	Incorrect	3 ms	748 KB	Output isn't correct
24	Incorrect	2 ms	748 KB	Output isn't correct
25	Incorrect	2 ms	748 KB	Output isn't correct
26	Incorrect	2 ms	748 KB	Output isn't correct
27	Correct	3 ms	748 KB	Output is correct
28	Correct	3 ms	748 KB	Output is correct
29	Incorrect	2 ms	748 KB	Output isn't correct
30	Incorrect	3 ms	748 KB	Output isn't correct
31	Incorrect	2 ms	748 KB	Output isn't correct
32	Incorrect	2 ms	748 KB	Output isn't correct
33	Correct	2 ms	748 KB	Output is correct
34	Correct	2 ms	748 KB	Output is correct
35	Correct	2 ms	748 KB	Output is correct

Subtask #3
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	748 KB	Output is correct
3	Correct	3 ms	748 KB	Output is correct
4	Incorrect	4 ms	764 KB	Output isn't correct
5	Incorrect	123 ms	9940 KB	Output isn't correct
6	Incorrect	110 ms	9940 KB	Output isn't correct
7	Incorrect	100 ms	9980 KB	Output isn't correct
8	Incorrect	2 ms	9980 KB	Output isn't correct
9	Incorrect	109 ms	9980 KB	Output isn't correct
10	Incorrect	107 ms	9980 KB	Output isn't correct
11	Incorrect	75 ms	9980 KB	Output isn't correct
12	Incorrect	119 ms	10032 KB	Output isn't correct
13	Incorrect	107 ms	10032 KB	Output isn't correct
14	Incorrect	87 ms	10108 KB	Output isn't correct
15	Correct	110 ms	10108 KB	Output is correct
16	Incorrect	118 ms	10108 KB	Output isn't correct
17	Incorrect	112 ms	10108 KB	Output isn't correct
18	Incorrect	118 ms	10108 KB	Output isn't correct
19	Incorrect	157 ms	10108 KB	Output isn't correct

Subtask #4
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Incorrect	2 ms	432 KB	Output isn't correct
4	Incorrect	2 ms	564 KB	Output isn't correct
5	Correct	2 ms	564 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Incorrect	3 ms	564 KB	Output isn't correct
8	Incorrect	2 ms	572 KB	Output isn't correct
9	Correct	2 ms	736 KB	Output is correct
10	Incorrect	2 ms	736 KB	Output isn't correct
11	Correct	2 ms	736 KB	Output is correct
12	Incorrect	3 ms	736 KB	Output isn't correct
13	Correct	2 ms	736 KB	Output is correct
14	Correct	2 ms	736 KB	Output is correct
15	Incorrect	2 ms	736 KB	Output isn't correct
16	Incorrect	3 ms	736 KB	Output isn't correct
17	Correct	2 ms	736 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Incorrect	2 ms	748 KB	Output isn't correct
20	Incorrect	3 ms	748 KB	Output isn't correct
21	Correct	2 ms	748 KB	Output is correct
22	Incorrect	2 ms	748 KB	Output isn't correct
23	Incorrect	3 ms	748 KB	Output isn't correct
24	Incorrect	2 ms	748 KB	Output isn't correct
25	Incorrect	2 ms	748 KB	Output isn't correct
26	Incorrect	2 ms	748 KB	Output isn't correct
27	Correct	3 ms	748 KB	Output is correct
28	Correct	3 ms	748 KB	Output is correct
29	Incorrect	2 ms	748 KB	Output isn't correct
30	Incorrect	3 ms	748 KB	Output isn't correct
31	Incorrect	2 ms	748 KB	Output isn't correct
32	Incorrect	2 ms	748 KB	Output isn't correct
33	Correct	2 ms	748 KB	Output is correct
34	Correct	2 ms	748 KB	Output is correct
35	Correct	2 ms	748 KB	Output is correct
36	Incorrect	6 ms	10108 KB	Output isn't correct
37	Incorrect	4 ms	10108 KB	Output isn't correct
38	Incorrect	4 ms	10108 KB	Output isn't correct
39	Incorrect	4 ms	10108 KB	Output isn't correct
40	Correct	5 ms	10108 KB	Output is correct
41	Correct	7 ms	10108 KB	Output is correct
42	Incorrect	6 ms	10108 KB	Output isn't correct
43	Incorrect	2 ms	10108 KB	Output isn't correct
44	Incorrect	5 ms	10108 KB	Output isn't correct
45	Correct	4 ms	10108 KB	Output is correct
46	Incorrect	5 ms	10108 KB	Output isn't correct
47	Incorrect	5 ms	10108 KB	Output isn't correct
48	Incorrect	5 ms	10108 KB	Output isn't correct
49	Incorrect	5 ms	10108 KB	Output isn't correct
50	Incorrect	4 ms	10108 KB	Output isn't correct
51	Incorrect	5 ms	10108 KB	Output isn't correct
52	Incorrect	3 ms	10108 KB	Output isn't correct
53	Correct	5 ms	10108 KB	Output is correct
54	Incorrect	4 ms	10108 KB	Output isn't correct
55	Correct	6 ms	10108 KB	Output is correct

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Incorrect	2 ms	432 KB	Output isn't correct
4	Incorrect	2 ms	564 KB	Output isn't correct
5	Correct	2 ms	564 KB	Output is correct
6	Correct	2 ms	564 KB	Output is correct
7	Incorrect	3 ms	564 KB	Output isn't correct
8	Incorrect	2 ms	572 KB	Output isn't correct
9	Correct	2 ms	736 KB	Output is correct
10	Incorrect	2 ms	736 KB	Output isn't correct
11	Correct	2 ms	736 KB	Output is correct
12	Incorrect	3 ms	736 KB	Output isn't correct
13	Correct	2 ms	736 KB	Output is correct
14	Correct	2 ms	736 KB	Output is correct
15	Incorrect	2 ms	736 KB	Output isn't correct
16	Incorrect	3 ms	736 KB	Output isn't correct
17	Correct	2 ms	736 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Incorrect	2 ms	748 KB	Output isn't correct
20	Incorrect	3 ms	748 KB	Output isn't correct
21	Correct	2 ms	748 KB	Output is correct
22	Incorrect	2 ms	748 KB	Output isn't correct
23	Incorrect	3 ms	748 KB	Output isn't correct
24	Incorrect	2 ms	748 KB	Output isn't correct
25	Incorrect	2 ms	748 KB	Output isn't correct
26	Incorrect	2 ms	748 KB	Output isn't correct
27	Correct	3 ms	748 KB	Output is correct
28	Correct	3 ms	748 KB	Output is correct
29	Incorrect	2 ms	748 KB	Output isn't correct
30	Incorrect	3 ms	748 KB	Output isn't correct
31	Incorrect	2 ms	748 KB	Output isn't correct
32	Incorrect	2 ms	748 KB	Output isn't correct
33	Correct	2 ms	748 KB	Output is correct
34	Correct	2 ms	748 KB	Output is correct
35	Correct	2 ms	748 KB	Output is correct
36	Correct	2 ms	748 KB	Output is correct
37	Correct	2 ms	748 KB	Output is correct
38	Correct	3 ms	748 KB	Output is correct
39	Incorrect	4 ms	764 KB	Output isn't correct
40	Incorrect	123 ms	9940 KB	Output isn't correct
41	Incorrect	110 ms	9940 KB	Output isn't correct
42	Incorrect	100 ms	9980 KB	Output isn't correct
43	Incorrect	2 ms	9980 KB	Output isn't correct
44	Incorrect	109 ms	9980 KB	Output isn't correct
45	Incorrect	107 ms	9980 KB	Output isn't correct
46	Incorrect	75 ms	9980 KB	Output isn't correct
47	Incorrect	119 ms	10032 KB	Output isn't correct
48	Incorrect	107 ms	10032 KB	Output isn't correct
49	Incorrect	87 ms	10108 KB	Output isn't correct
50	Correct	110 ms	10108 KB	Output is correct
51	Incorrect	118 ms	10108 KB	Output isn't correct
52	Incorrect	112 ms	10108 KB	Output isn't correct
53	Incorrect	118 ms	10108 KB	Output isn't correct
54	Incorrect	157 ms	10108 KB	Output isn't correct
55	Incorrect	6 ms	10108 KB	Output isn't correct
56	Incorrect	4 ms	10108 KB	Output isn't correct
57	Incorrect	4 ms	10108 KB	Output isn't correct
58	Incorrect	4 ms	10108 KB	Output isn't correct
59	Correct	5 ms	10108 KB	Output is correct
60	Correct	7 ms	10108 KB	Output is correct
61	Incorrect	6 ms	10108 KB	Output isn't correct
62	Incorrect	2 ms	10108 KB	Output isn't correct
63	Incorrect	5 ms	10108 KB	Output isn't correct
64	Correct	4 ms	10108 KB	Output is correct
65	Incorrect	5 ms	10108 KB	Output isn't correct
66	Incorrect	5 ms	10108 KB	Output isn't correct
67	Incorrect	5 ms	10108 KB	Output isn't correct
68	Incorrect	5 ms	10108 KB	Output isn't correct
69	Incorrect	4 ms	10108 KB	Output isn't correct
70	Incorrect	5 ms	10108 KB	Output isn't correct
71	Incorrect	3 ms	10108 KB	Output isn't correct
72	Correct	5 ms	10108 KB	Output is correct
73	Incorrect	4 ms	10108 KB	Output isn't correct
74	Correct	6 ms	10108 KB	Output is correct
75	Incorrect	157 ms	10108 KB	Output isn't correct
76	Incorrect	102 ms	10108 KB	Output isn't correct
77	Incorrect	114 ms	10108 KB	Output isn't correct
78	Incorrect	63 ms	10108 KB	Output isn't correct
79	Correct	139 ms	10108 KB	Output is correct
80	Incorrect	162 ms	10108 KB	Output isn't correct
81	Incorrect	5 ms	10108 KB	Output isn't correct
82	Incorrect	140 ms	10108 KB	Output isn't correct
83	Correct	69 ms	10112 KB	Output is correct
84	Incorrect	144 ms	10112 KB	Output isn't correct
85	Incorrect	154 ms	10112 KB	Output isn't correct
86	Incorrect	154 ms	10112 KB	Output isn't correct
87	Incorrect	93 ms	10112 KB	Output isn't correct
88	Incorrect	93 ms	10112 KB	Output isn't correct
89	Incorrect	174 ms	10112 KB	Output isn't correct
90	Incorrect	174 ms	10112 KB	Output isn't correct
91	Incorrect	159 ms	10112 KB	Output isn't correct
92	Correct	142 ms	10112 KB	Output is correct
93	Incorrect	136 ms	10112 KB	Output isn't correct
94	Incorrect	144 ms	10112 KB	Output isn't correct
95	Incorrect	142 ms	10112 KB	Output isn't correct

Submission #66306

Compilation message

Subtask #1 0 / 10.0

Subtask #2 0 / 8.0

Subtask #3 0 / 25.0

Subtask #4 0 / 27.0

Subtask #5 0 / 30.0

Subtask #1
0 / 10.0

Subtask #2
0 / 8.0

Subtask #3
0 / 25.0

Subtask #4
0 / 27.0

Subtask #5
0 / 30.0