Submission #66303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
66303	2018-08-10T07:49:18 Z	정원준(#1889)	초음속철도 (OJUZ11_rail)	C++11	0 / 100	189 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	340 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Incorrect	2 ms	484 KB	Output isn't correct
4	Incorrect	3 ms	512 KB	Output isn't correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Incorrect	2 ms	556 KB	Output isn't correct
8	Incorrect	2 ms	556 KB	Output isn't correct
9	Correct	2 ms	556 KB	Output is correct
10	Incorrect	2 ms	556 KB	Output isn't correct
11	Correct	2 ms	604 KB	Output is correct
12	Incorrect	2 ms	604 KB	Output isn't correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Incorrect	2 ms	716 KB	Output isn't correct
16	Incorrect	2 ms	716 KB	Output isn't correct
17	Correct	2 ms	716 KB	Output is correct
18	Correct	2 ms	716 KB	Output is correct

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Incorrect	2 ms	484 KB	Output isn't correct
4	Incorrect	3 ms	512 KB	Output isn't correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Incorrect	2 ms	556 KB	Output isn't correct
8	Incorrect	2 ms	556 KB	Output isn't correct
9	Correct	2 ms	556 KB	Output is correct
10	Incorrect	2 ms	556 KB	Output isn't correct
11	Correct	2 ms	604 KB	Output is correct
12	Incorrect	2 ms	604 KB	Output isn't correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Incorrect	2 ms	716 KB	Output isn't correct
16	Incorrect	2 ms	716 KB	Output isn't correct
17	Correct	2 ms	716 KB	Output is correct
18	Correct	2 ms	716 KB	Output is correct
19	Incorrect	3 ms	716 KB	Output isn't correct
20	Incorrect	2 ms	716 KB	Output isn't correct
21	Correct	2 ms	716 KB	Output is correct
22	Incorrect	2 ms	716 KB	Output isn't correct
23	Incorrect	2 ms	716 KB	Output isn't correct
24	Incorrect	2 ms	716 KB	Output isn't correct
25	Incorrect	2 ms	716 KB	Output isn't correct
26	Incorrect	2 ms	716 KB	Output isn't correct
27	Correct	2 ms	716 KB	Output is correct
28	Correct	2 ms	716 KB	Output is correct
29	Incorrect	2 ms	748 KB	Output isn't correct
30	Incorrect	2 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	2 ms	748 KB	Output is correct
4	Incorrect	3 ms	764 KB	Output isn't correct
5	Incorrect	89 ms	10008 KB	Output isn't correct
6	Incorrect	103 ms	10008 KB	Output isn't correct
7	Incorrect	95 ms	10080 KB	Output isn't correct
8	Incorrect	2 ms	10080 KB	Output isn't correct
9	Incorrect	99 ms	10080 KB	Output isn't correct
10	Incorrect	108 ms	10080 KB	Output isn't correct
11	Incorrect	48 ms	10080 KB	Output isn't correct
12	Incorrect	129 ms	10080 KB	Output isn't correct
13	Incorrect	107 ms	10080 KB	Output isn't correct
14	Incorrect	68 ms	10080 KB	Output isn't correct
15	Correct	125 ms	10080 KB	Output is correct
16	Incorrect	84 ms	10080 KB	Output isn't correct
17	Incorrect	113 ms	10080 KB	Output isn't correct
18	Incorrect	110 ms	10080 KB	Output isn't correct
19	Incorrect	115 ms	10080 KB	Output isn't correct

Subtask #4
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Incorrect	2 ms	484 KB	Output isn't correct
4	Incorrect	3 ms	512 KB	Output isn't correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Incorrect	2 ms	556 KB	Output isn't correct
8	Incorrect	2 ms	556 KB	Output isn't correct
9	Correct	2 ms	556 KB	Output is correct
10	Incorrect	2 ms	556 KB	Output isn't correct
11	Correct	2 ms	604 KB	Output is correct
12	Incorrect	2 ms	604 KB	Output isn't correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Incorrect	2 ms	716 KB	Output isn't correct
16	Incorrect	2 ms	716 KB	Output isn't correct
17	Correct	2 ms	716 KB	Output is correct
18	Correct	2 ms	716 KB	Output is correct
19	Incorrect	3 ms	716 KB	Output isn't correct
20	Incorrect	2 ms	716 KB	Output isn't correct
21	Correct	2 ms	716 KB	Output is correct
22	Incorrect	2 ms	716 KB	Output isn't correct
23	Incorrect	2 ms	716 KB	Output isn't correct
24	Incorrect	2 ms	716 KB	Output isn't correct
25	Incorrect	2 ms	716 KB	Output isn't correct
26	Incorrect	2 ms	716 KB	Output isn't correct
27	Correct	2 ms	716 KB	Output is correct
28	Correct	2 ms	716 KB	Output is correct
29	Incorrect	2 ms	748 KB	Output isn't correct
30	Incorrect	2 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	5 ms	10080 KB	Output isn't correct
37	Incorrect	6 ms	10080 KB	Output isn't correct
38	Incorrect	5 ms	10080 KB	Output isn't correct
39	Incorrect	4 ms	10080 KB	Output isn't correct
40	Correct	5 ms	10080 KB	Output is correct
41	Correct	5 ms	10080 KB	Output is correct
42	Incorrect	6 ms	10080 KB	Output isn't correct
43	Incorrect	3 ms	10080 KB	Output isn't correct
44	Incorrect	5 ms	10080 KB	Output isn't correct
45	Correct	4 ms	10080 KB	Output is correct
46	Incorrect	4 ms	10080 KB	Output isn't correct
47	Incorrect	6 ms	10080 KB	Output isn't correct
48	Incorrect	6 ms	10080 KB	Output isn't correct
49	Incorrect	5 ms	10080 KB	Output isn't correct
50	Incorrect	5 ms	10080 KB	Output isn't correct
51	Incorrect	4 ms	10080 KB	Output isn't correct
52	Incorrect	2 ms	10080 KB	Output isn't correct
53	Correct	5 ms	10080 KB	Output is correct
54	Incorrect	4 ms	10080 KB	Output isn't correct
55	Correct	5 ms	10080 KB	Output is correct

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Incorrect	2 ms	484 KB	Output isn't correct
4	Incorrect	3 ms	512 KB	Output isn't correct
5	Correct	2 ms	536 KB	Output is correct
6	Correct	2 ms	536 KB	Output is correct
7	Incorrect	2 ms	556 KB	Output isn't correct
8	Incorrect	2 ms	556 KB	Output isn't correct
9	Correct	2 ms	556 KB	Output is correct
10	Incorrect	2 ms	556 KB	Output isn't correct
11	Correct	2 ms	604 KB	Output is correct
12	Incorrect	2 ms	604 KB	Output isn't correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Incorrect	2 ms	716 KB	Output isn't correct
16	Incorrect	2 ms	716 KB	Output isn't correct
17	Correct	2 ms	716 KB	Output is correct
18	Correct	2 ms	716 KB	Output is correct
19	Incorrect	3 ms	716 KB	Output isn't correct
20	Incorrect	2 ms	716 KB	Output isn't correct
21	Correct	2 ms	716 KB	Output is correct
22	Incorrect	2 ms	716 KB	Output isn't correct
23	Incorrect	2 ms	716 KB	Output isn't correct
24	Incorrect	2 ms	716 KB	Output isn't correct
25	Incorrect	2 ms	716 KB	Output isn't correct
26	Incorrect	2 ms	716 KB	Output isn't correct
27	Correct	2 ms	716 KB	Output is correct
28	Correct	2 ms	716 KB	Output is correct
29	Incorrect	2 ms	748 KB	Output isn't correct
30	Incorrect	2 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	2 ms	748 KB	Output is correct
39	Incorrect	3 ms	764 KB	Output isn't correct
40	Incorrect	89 ms	10008 KB	Output isn't correct
41	Incorrect	103 ms	10008 KB	Output isn't correct
42	Incorrect	95 ms	10080 KB	Output isn't correct
43	Incorrect	2 ms	10080 KB	Output isn't correct
44	Incorrect	99 ms	10080 KB	Output isn't correct
45	Incorrect	108 ms	10080 KB	Output isn't correct
46	Incorrect	48 ms	10080 KB	Output isn't correct
47	Incorrect	129 ms	10080 KB	Output isn't correct
48	Incorrect	107 ms	10080 KB	Output isn't correct
49	Incorrect	68 ms	10080 KB	Output isn't correct
50	Correct	125 ms	10080 KB	Output is correct
51	Incorrect	84 ms	10080 KB	Output isn't correct
52	Incorrect	113 ms	10080 KB	Output isn't correct
53	Incorrect	110 ms	10080 KB	Output isn't correct
54	Incorrect	115 ms	10080 KB	Output isn't correct
55	Incorrect	5 ms	10080 KB	Output isn't correct
56	Incorrect	6 ms	10080 KB	Output isn't correct
57	Incorrect	5 ms	10080 KB	Output isn't correct
58	Incorrect	4 ms	10080 KB	Output isn't correct
59	Correct	5 ms	10080 KB	Output is correct
60	Correct	5 ms	10080 KB	Output is correct
61	Incorrect	6 ms	10080 KB	Output isn't correct
62	Incorrect	3 ms	10080 KB	Output isn't correct
63	Incorrect	5 ms	10080 KB	Output isn't correct
64	Correct	4 ms	10080 KB	Output is correct
65	Incorrect	4 ms	10080 KB	Output isn't correct
66	Incorrect	6 ms	10080 KB	Output isn't correct
67	Incorrect	6 ms	10080 KB	Output isn't correct
68	Incorrect	5 ms	10080 KB	Output isn't correct
69	Incorrect	5 ms	10080 KB	Output isn't correct
70	Incorrect	4 ms	10080 KB	Output isn't correct
71	Incorrect	2 ms	10080 KB	Output isn't correct
72	Correct	5 ms	10080 KB	Output is correct
73	Incorrect	4 ms	10080 KB	Output isn't correct
74	Correct	5 ms	10080 KB	Output is correct
75	Incorrect	159 ms	10080 KB	Output isn't correct
76	Incorrect	89 ms	10080 KB	Output isn't correct
77	Incorrect	115 ms	10080 KB	Output isn't correct
78	Incorrect	78 ms	10080 KB	Output isn't correct
79	Correct	142 ms	10080 KB	Output is correct
80	Incorrect	189 ms	10080 KB	Output isn't correct
81	Incorrect	4 ms	10080 KB	Output isn't correct
82	Incorrect	137 ms	10080 KB	Output isn't correct
83	Correct	63 ms	10080 KB	Output is correct
84	Incorrect	137 ms	10080 KB	Output isn't correct
85	Incorrect	137 ms	10080 KB	Output isn't correct
86	Incorrect	149 ms	10080 KB	Output isn't correct
87	Incorrect	90 ms	10108 KB	Output isn't correct
88	Incorrect	89 ms	10108 KB	Output isn't correct
89	Incorrect	155 ms	10108 KB	Output isn't correct
90	Incorrect	160 ms	10108 KB	Output isn't correct
91	Incorrect	160 ms	10108 KB	Output isn't correct
92	Correct	142 ms	10108 KB	Output is correct
93	Incorrect	137 ms	10108 KB	Output isn't correct
94	Incorrect	145 ms	10124 KB	Output isn't correct
95	Incorrect	149 ms	10124 KB	Output isn't correct

Submission #66303

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