Submission #66299

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
66299	2018-08-10T07:42:49 Z	정원준(#1889)	초음속철도 (OJUZ11_rail)	C++11	0 / 100	197 ms	10124 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	4 ms	360 KB	Output is correct
3	Incorrect	2 ms	392 KB	Output isn't correct
4	Incorrect	2 ms	472 KB	Output isn't correct
5	Correct	2 ms	580 KB	Output is correct
6	Correct	2 ms	580 KB	Output is correct
7	Incorrect	2 ms	580 KB	Output isn't correct
8	Incorrect	3 ms	620 KB	Output isn't correct
9	Correct	3 ms	620 KB	Output is correct
10	Incorrect	3 ms	748 KB	Output isn't correct
11	Correct	2 ms	748 KB	Output is correct
12	Incorrect	3 ms	748 KB	Output isn't correct
13	Correct	3 ms	748 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Incorrect	3 ms	748 KB	Output isn't correct
16	Incorrect	2 ms	748 KB	Output isn't correct
17	Correct	2 ms	748 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	4 ms	360 KB	Output is correct
3	Incorrect	2 ms	392 KB	Output isn't correct
4	Incorrect	2 ms	472 KB	Output isn't correct
5	Correct	2 ms	580 KB	Output is correct
6	Correct	2 ms	580 KB	Output is correct
7	Incorrect	2 ms	580 KB	Output isn't correct
8	Incorrect	3 ms	620 KB	Output isn't correct
9	Correct	3 ms	620 KB	Output is correct
10	Incorrect	3 ms	748 KB	Output isn't correct
11	Correct	2 ms	748 KB	Output is correct
12	Incorrect	3 ms	748 KB	Output isn't correct
13	Correct	3 ms	748 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Incorrect	3 ms	748 KB	Output isn't correct
16	Incorrect	2 ms	748 KB	Output isn't correct
17	Correct	2 ms	748 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Incorrect	3 ms	748 KB	Output isn't correct
20	Incorrect	2 ms	748 KB	Output isn't correct
21	Correct	2 ms	752 KB	Output is correct
22	Incorrect	2 ms	752 KB	Output isn't correct
23	Incorrect	2 ms	752 KB	Output isn't correct
24	Incorrect	2 ms	752 KB	Output isn't correct
25	Incorrect	3 ms	752 KB	Output isn't correct
26	Incorrect	2 ms	752 KB	Output isn't correct
27	Correct	2 ms	752 KB	Output is correct
28	Correct	2 ms	752 KB	Output is correct
29	Incorrect	2 ms	752 KB	Output isn't correct
30	Incorrect	3 ms	752 KB	Output isn't correct
31	Incorrect	2 ms	752 KB	Output isn't correct
32	Incorrect	2 ms	752 KB	Output isn't correct
33	Correct	2 ms	752 KB	Output is correct
34	Correct	2 ms	752 KB	Output is correct
35	Correct	3 ms	752 KB	Output is correct

Subtask #3
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	752 KB	Output is correct
2	Correct	3 ms	752 KB	Output is correct
3	Correct	2 ms	752 KB	Output is correct
4	Incorrect	4 ms	764 KB	Output isn't correct
5	Incorrect	102 ms	9952 KB	Output isn't correct
6	Incorrect	157 ms	9952 KB	Output isn't correct
7	Incorrect	105 ms	9952 KB	Output isn't correct
8	Incorrect	3 ms	9952 KB	Output isn't correct
9	Incorrect	96 ms	9952 KB	Output isn't correct
10	Incorrect	116 ms	9952 KB	Output isn't correct
11	Incorrect	48 ms	9952 KB	Output isn't correct
12	Incorrect	121 ms	9976 KB	Output isn't correct
13	Incorrect	99 ms	9976 KB	Output isn't correct
14	Incorrect	68 ms	9980 KB	Output isn't correct
15	Correct	102 ms	9980 KB	Output is correct
16	Incorrect	70 ms	9980 KB	Output isn't correct
17	Incorrect	102 ms	9980 KB	Output isn't correct
18	Incorrect	111 ms	9980 KB	Output isn't correct
19	Incorrect	110 ms	9980 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	4 ms	360 KB	Output is correct
3	Incorrect	2 ms	392 KB	Output isn't correct
4	Incorrect	2 ms	472 KB	Output isn't correct
5	Correct	2 ms	580 KB	Output is correct
6	Correct	2 ms	580 KB	Output is correct
7	Incorrect	2 ms	580 KB	Output isn't correct
8	Incorrect	3 ms	620 KB	Output isn't correct
9	Correct	3 ms	620 KB	Output is correct
10	Incorrect	3 ms	748 KB	Output isn't correct
11	Correct	2 ms	748 KB	Output is correct
12	Incorrect	3 ms	748 KB	Output isn't correct
13	Correct	3 ms	748 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Incorrect	3 ms	748 KB	Output isn't correct
16	Incorrect	2 ms	748 KB	Output isn't correct
17	Correct	2 ms	748 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Incorrect	3 ms	748 KB	Output isn't correct
20	Incorrect	2 ms	748 KB	Output isn't correct
21	Correct	2 ms	752 KB	Output is correct
22	Incorrect	2 ms	752 KB	Output isn't correct
23	Incorrect	2 ms	752 KB	Output isn't correct
24	Incorrect	2 ms	752 KB	Output isn't correct
25	Incorrect	3 ms	752 KB	Output isn't correct
26	Incorrect	2 ms	752 KB	Output isn't correct
27	Correct	2 ms	752 KB	Output is correct
28	Correct	2 ms	752 KB	Output is correct
29	Incorrect	2 ms	752 KB	Output isn't correct
30	Incorrect	3 ms	752 KB	Output isn't correct
31	Incorrect	2 ms	752 KB	Output isn't correct
32	Incorrect	2 ms	752 KB	Output isn't correct
33	Correct	2 ms	752 KB	Output is correct
34	Correct	2 ms	752 KB	Output is correct
35	Correct	3 ms	752 KB	Output is correct
36	Incorrect	6 ms	9980 KB	Output isn't correct
37	Incorrect	6 ms	9980 KB	Output isn't correct
38	Incorrect	4 ms	9980 KB	Output isn't correct
39	Incorrect	5 ms	9980 KB	Output isn't correct
40	Correct	6 ms	9980 KB	Output is correct
41	Correct	5 ms	9980 KB	Output is correct
42	Incorrect	6 ms	9980 KB	Output isn't correct
43	Incorrect	2 ms	9980 KB	Output isn't correct
44	Incorrect	5 ms	9980 KB	Output isn't correct
45	Correct	4 ms	9980 KB	Output is correct
46	Incorrect	5 ms	9980 KB	Output isn't correct
47	Incorrect	5 ms	9980 KB	Output isn't correct
48	Incorrect	6 ms	9980 KB	Output isn't correct
49	Incorrect	4 ms	9980 KB	Output isn't correct
50	Incorrect	5 ms	9980 KB	Output isn't correct
51	Incorrect	4 ms	9980 KB	Output isn't correct
52	Incorrect	3 ms	9980 KB	Output isn't correct
53	Correct	5 ms	9980 KB	Output is correct
54	Incorrect	4 ms	9980 KB	Output isn't correct
55	Correct	5 ms	9980 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	4 ms	360 KB	Output is correct
3	Incorrect	2 ms	392 KB	Output isn't correct
4	Incorrect	2 ms	472 KB	Output isn't correct
5	Correct	2 ms	580 KB	Output is correct
6	Correct	2 ms	580 KB	Output is correct
7	Incorrect	2 ms	580 KB	Output isn't correct
8	Incorrect	3 ms	620 KB	Output isn't correct
9	Correct	3 ms	620 KB	Output is correct
10	Incorrect	3 ms	748 KB	Output isn't correct
11	Correct	2 ms	748 KB	Output is correct
12	Incorrect	3 ms	748 KB	Output isn't correct
13	Correct	3 ms	748 KB	Output is correct
14	Correct	2 ms	748 KB	Output is correct
15	Incorrect	3 ms	748 KB	Output isn't correct
16	Incorrect	2 ms	748 KB	Output isn't correct
17	Correct	2 ms	748 KB	Output is correct
18	Correct	2 ms	748 KB	Output is correct
19	Incorrect	3 ms	748 KB	Output isn't correct
20	Incorrect	2 ms	748 KB	Output isn't correct
21	Correct	2 ms	752 KB	Output is correct
22	Incorrect	2 ms	752 KB	Output isn't correct
23	Incorrect	2 ms	752 KB	Output isn't correct
24	Incorrect	2 ms	752 KB	Output isn't correct
25	Incorrect	3 ms	752 KB	Output isn't correct
26	Incorrect	2 ms	752 KB	Output isn't correct
27	Correct	2 ms	752 KB	Output is correct
28	Correct	2 ms	752 KB	Output is correct
29	Incorrect	2 ms	752 KB	Output isn't correct
30	Incorrect	3 ms	752 KB	Output isn't correct
31	Incorrect	2 ms	752 KB	Output isn't correct
32	Incorrect	2 ms	752 KB	Output isn't correct
33	Correct	2 ms	752 KB	Output is correct
34	Correct	2 ms	752 KB	Output is correct
35	Correct	3 ms	752 KB	Output is correct
36	Correct	2 ms	752 KB	Output is correct
37	Correct	3 ms	752 KB	Output is correct
38	Correct	2 ms	752 KB	Output is correct
39	Incorrect	4 ms	764 KB	Output isn't correct
40	Incorrect	102 ms	9952 KB	Output isn't correct
41	Incorrect	157 ms	9952 KB	Output isn't correct
42	Incorrect	105 ms	9952 KB	Output isn't correct
43	Incorrect	3 ms	9952 KB	Output isn't correct
44	Incorrect	96 ms	9952 KB	Output isn't correct
45	Incorrect	116 ms	9952 KB	Output isn't correct
46	Incorrect	48 ms	9952 KB	Output isn't correct
47	Incorrect	121 ms	9976 KB	Output isn't correct
48	Incorrect	99 ms	9976 KB	Output isn't correct
49	Incorrect	68 ms	9980 KB	Output isn't correct
50	Correct	102 ms	9980 KB	Output is correct
51	Incorrect	70 ms	9980 KB	Output isn't correct
52	Incorrect	102 ms	9980 KB	Output isn't correct
53	Incorrect	111 ms	9980 KB	Output isn't correct
54	Incorrect	110 ms	9980 KB	Output isn't correct
55	Incorrect	6 ms	9980 KB	Output isn't correct
56	Incorrect	6 ms	9980 KB	Output isn't correct
57	Incorrect	4 ms	9980 KB	Output isn't correct
58	Incorrect	5 ms	9980 KB	Output isn't correct
59	Correct	6 ms	9980 KB	Output is correct
60	Correct	5 ms	9980 KB	Output is correct
61	Incorrect	6 ms	9980 KB	Output isn't correct
62	Incorrect	2 ms	9980 KB	Output isn't correct
63	Incorrect	5 ms	9980 KB	Output isn't correct
64	Correct	4 ms	9980 KB	Output is correct
65	Incorrect	5 ms	9980 KB	Output isn't correct
66	Incorrect	5 ms	9980 KB	Output isn't correct
67	Incorrect	6 ms	9980 KB	Output isn't correct
68	Incorrect	4 ms	9980 KB	Output isn't correct
69	Incorrect	5 ms	9980 KB	Output isn't correct
70	Incorrect	4 ms	9980 KB	Output isn't correct
71	Incorrect	3 ms	9980 KB	Output isn't correct
72	Correct	5 ms	9980 KB	Output is correct
73	Incorrect	4 ms	9980 KB	Output isn't correct
74	Correct	5 ms	9980 KB	Output is correct
75	Incorrect	197 ms	9980 KB	Output isn't correct
76	Incorrect	92 ms	9980 KB	Output isn't correct
77	Incorrect	121 ms	9980 KB	Output isn't correct
78	Incorrect	68 ms	9980 KB	Output isn't correct
79	Correct	133 ms	9980 KB	Output is correct
80	Incorrect	145 ms	9980 KB	Output isn't correct
81	Incorrect	5 ms	9980 KB	Output isn't correct
82	Incorrect	181 ms	9980 KB	Output isn't correct
83	Correct	114 ms	9980 KB	Output is correct
84	Incorrect	163 ms	10100 KB	Output isn't correct
85	Incorrect	131 ms	10100 KB	Output isn't correct
86	Incorrect	131 ms	10100 KB	Output isn't correct
87	Incorrect	97 ms	10100 KB	Output isn't correct
88	Incorrect	97 ms	10100 KB	Output isn't correct
89	Incorrect	161 ms	10100 KB	Output isn't correct
90	Incorrect	159 ms	10124 KB	Output isn't correct
91	Incorrect	159 ms	10124 KB	Output isn't correct
92	Correct	165 ms	10124 KB	Output is correct
93	Incorrect	135 ms	10124 KB	Output isn't correct
94	Incorrect	193 ms	10124 KB	Output isn't correct
95	Incorrect	160 ms	10124 KB	Output isn't correct

Submission #66299

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