답안 #66298 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66298	2018-08-10T07:40:03 Z	정원준(#1889)	초음속철도 (OJUZ11_rail)	C++11	0 / 100	174 ms	10068 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;
	dp[0][0]=1;
	ds[0][0]=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]-ds[S-1][0]-ds[S-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];
		}
		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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Incorrect	2 ms	488 KB	Output isn't correct
3	Incorrect	2 ms	488 KB	Output isn't correct
4	Incorrect	3 ms	548 KB	Output isn't correct
5	Correct	2 ms	548 KB	Output is correct
6	Incorrect	3 ms	548 KB	Output isn't correct
7	Incorrect	2 ms	560 KB	Output isn't correct
8	Incorrect	2 ms	608 KB	Output isn't correct
9	Correct	2 ms	612 KB	Output is correct
10	Incorrect	2 ms	612 KB	Output isn't correct
11	Incorrect	2 ms	612 KB	Output isn't correct
12	Incorrect	2 ms	612 KB	Output isn't correct
13	Incorrect	2 ms	680 KB	Output isn't correct
14	Incorrect	3 ms	680 KB	Output isn't correct
15	Incorrect	3 ms	680 KB	Output isn't correct
16	Incorrect	3 ms	680 KB	Output isn't correct
17	Correct	3 ms	680 KB	Output is correct
18	Correct	3 ms	680 KB	Output is correct

Subtask #2
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Incorrect	2 ms	488 KB	Output isn't correct
3	Incorrect	2 ms	488 KB	Output isn't correct
4	Incorrect	3 ms	548 KB	Output isn't correct
5	Correct	2 ms	548 KB	Output is correct
6	Incorrect	3 ms	548 KB	Output isn't correct
7	Incorrect	2 ms	560 KB	Output isn't correct
8	Incorrect	2 ms	608 KB	Output isn't correct
9	Correct	2 ms	612 KB	Output is correct
10	Incorrect	2 ms	612 KB	Output isn't correct
11	Incorrect	2 ms	612 KB	Output isn't correct
12	Incorrect	2 ms	612 KB	Output isn't correct
13	Incorrect	2 ms	680 KB	Output isn't correct
14	Incorrect	3 ms	680 KB	Output isn't correct
15	Incorrect	3 ms	680 KB	Output isn't correct
16	Incorrect	3 ms	680 KB	Output isn't correct
17	Correct	3 ms	680 KB	Output is correct
18	Correct	3 ms	680 KB	Output is correct
19	Incorrect	2 ms	680 KB	Output isn't correct
20	Incorrect	2 ms	680 KB	Output isn't correct
21	Incorrect	2 ms	680 KB	Output isn't correct
22	Incorrect	3 ms	680 KB	Output isn't correct
23	Incorrect	2 ms	680 KB	Output isn't correct
24	Incorrect	3 ms	680 KB	Output isn't correct
25	Incorrect	2 ms	680 KB	Output isn't correct
26	Incorrect	2 ms	680 KB	Output isn't correct
27	Correct	3 ms	680 KB	Output is correct
28	Incorrect	2 ms	680 KB	Output isn't correct
29	Incorrect	2 ms	680 KB	Output isn't correct
30	Incorrect	2 ms	680 KB	Output isn't correct
31	Incorrect	2 ms	680 KB	Output isn't correct
32	Incorrect	2 ms	680 KB	Output isn't correct
33	Correct	2 ms	680 KB	Output is correct
34	Incorrect	2 ms	680 KB	Output isn't correct
35	Correct	2 ms	680 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	680 KB	Output isn't correct
2	Correct	3 ms	744 KB	Output is correct
3	Correct	3 ms	744 KB	Output is correct
4	Incorrect	4 ms	860 KB	Output isn't correct
5	Incorrect	92 ms	9916 KB	Output isn't correct
6	Incorrect	115 ms	9916 KB	Output isn't correct
7	Incorrect	99 ms	9964 KB	Output isn't correct
8	Incorrect	2 ms	9964 KB	Output isn't correct
9	Incorrect	116 ms	9964 KB	Output isn't correct
10	Incorrect	131 ms	9964 KB	Output isn't correct
11	Incorrect	59 ms	9964 KB	Output isn't correct
12	Incorrect	112 ms	9964 KB	Output isn't correct
13	Incorrect	120 ms	9964 KB	Output isn't correct
14	Incorrect	98 ms	9964 KB	Output isn't correct
15	Incorrect	114 ms	9964 KB	Output isn't correct
16	Incorrect	123 ms	9984 KB	Output isn't correct
17	Incorrect	117 ms	9984 KB	Output isn't correct
18	Incorrect	133 ms	9984 KB	Output isn't correct
19	Incorrect	122 ms	9984 KB	Output isn't correct

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Incorrect	2 ms	488 KB	Output isn't correct
3	Incorrect	2 ms	488 KB	Output isn't correct
4	Incorrect	3 ms	548 KB	Output isn't correct
5	Correct	2 ms	548 KB	Output is correct
6	Incorrect	3 ms	548 KB	Output isn't correct
7	Incorrect	2 ms	560 KB	Output isn't correct
8	Incorrect	2 ms	608 KB	Output isn't correct
9	Correct	2 ms	612 KB	Output is correct
10	Incorrect	2 ms	612 KB	Output isn't correct
11	Incorrect	2 ms	612 KB	Output isn't correct
12	Incorrect	2 ms	612 KB	Output isn't correct
13	Incorrect	2 ms	680 KB	Output isn't correct
14	Incorrect	3 ms	680 KB	Output isn't correct
15	Incorrect	3 ms	680 KB	Output isn't correct
16	Incorrect	3 ms	680 KB	Output isn't correct
17	Correct	3 ms	680 KB	Output is correct
18	Correct	3 ms	680 KB	Output is correct
19	Incorrect	2 ms	680 KB	Output isn't correct
20	Incorrect	2 ms	680 KB	Output isn't correct
21	Incorrect	2 ms	680 KB	Output isn't correct
22	Incorrect	3 ms	680 KB	Output isn't correct
23	Incorrect	2 ms	680 KB	Output isn't correct
24	Incorrect	3 ms	680 KB	Output isn't correct
25	Incorrect	2 ms	680 KB	Output isn't correct
26	Incorrect	2 ms	680 KB	Output isn't correct
27	Correct	3 ms	680 KB	Output is correct
28	Incorrect	2 ms	680 KB	Output isn't correct
29	Incorrect	2 ms	680 KB	Output isn't correct
30	Incorrect	2 ms	680 KB	Output isn't correct
31	Incorrect	2 ms	680 KB	Output isn't correct
32	Incorrect	2 ms	680 KB	Output isn't correct
33	Correct	2 ms	680 KB	Output is correct
34	Incorrect	2 ms	680 KB	Output isn't correct
35	Correct	2 ms	680 KB	Output is correct
36	Incorrect	5 ms	9984 KB	Output isn't correct
37	Incorrect	5 ms	9984 KB	Output isn't correct
38	Incorrect	4 ms	9984 KB	Output isn't correct
39	Incorrect	4 ms	9984 KB	Output isn't correct
40	Incorrect	5 ms	9984 KB	Output isn't correct
41	Correct	5 ms	9984 KB	Output is correct
42	Incorrect	5 ms	9984 KB	Output isn't correct
43	Incorrect	3 ms	9984 KB	Output isn't correct
44	Incorrect	5 ms	9984 KB	Output isn't correct
45	Incorrect	4 ms	9984 KB	Output isn't correct
46	Incorrect	6 ms	9984 KB	Output isn't correct
47	Incorrect	7 ms	9984 KB	Output isn't correct
48	Incorrect	6 ms	9984 KB	Output isn't correct
49	Incorrect	5 ms	9984 KB	Output isn't correct
50	Incorrect	4 ms	9984 KB	Output isn't correct
51	Incorrect	4 ms	9984 KB	Output isn't correct
52	Incorrect	3 ms	9984 KB	Output isn't correct
53	Correct	6 ms	9984 KB	Output is correct
54	Incorrect	4 ms	9984 KB	Output isn't correct
55	Correct	6 ms	9984 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Incorrect	2 ms	488 KB	Output isn't correct
3	Incorrect	2 ms	488 KB	Output isn't correct
4	Incorrect	3 ms	548 KB	Output isn't correct
5	Correct	2 ms	548 KB	Output is correct
6	Incorrect	3 ms	548 KB	Output isn't correct
7	Incorrect	2 ms	560 KB	Output isn't correct
8	Incorrect	2 ms	608 KB	Output isn't correct
9	Correct	2 ms	612 KB	Output is correct
10	Incorrect	2 ms	612 KB	Output isn't correct
11	Incorrect	2 ms	612 KB	Output isn't correct
12	Incorrect	2 ms	612 KB	Output isn't correct
13	Incorrect	2 ms	680 KB	Output isn't correct
14	Incorrect	3 ms	680 KB	Output isn't correct
15	Incorrect	3 ms	680 KB	Output isn't correct
16	Incorrect	3 ms	680 KB	Output isn't correct
17	Correct	3 ms	680 KB	Output is correct
18	Correct	3 ms	680 KB	Output is correct
19	Incorrect	2 ms	680 KB	Output isn't correct
20	Incorrect	2 ms	680 KB	Output isn't correct
21	Incorrect	2 ms	680 KB	Output isn't correct
22	Incorrect	3 ms	680 KB	Output isn't correct
23	Incorrect	2 ms	680 KB	Output isn't correct
24	Incorrect	3 ms	680 KB	Output isn't correct
25	Incorrect	2 ms	680 KB	Output isn't correct
26	Incorrect	2 ms	680 KB	Output isn't correct
27	Correct	3 ms	680 KB	Output is correct
28	Incorrect	2 ms	680 KB	Output isn't correct
29	Incorrect	2 ms	680 KB	Output isn't correct
30	Incorrect	2 ms	680 KB	Output isn't correct
31	Incorrect	2 ms	680 KB	Output isn't correct
32	Incorrect	2 ms	680 KB	Output isn't correct
33	Correct	2 ms	680 KB	Output is correct
34	Incorrect	2 ms	680 KB	Output isn't correct
35	Correct	2 ms	680 KB	Output is correct
36	Incorrect	2 ms	680 KB	Output isn't correct
37	Correct	3 ms	744 KB	Output is correct
38	Correct	3 ms	744 KB	Output is correct
39	Incorrect	4 ms	860 KB	Output isn't correct
40	Incorrect	92 ms	9916 KB	Output isn't correct
41	Incorrect	115 ms	9916 KB	Output isn't correct
42	Incorrect	99 ms	9964 KB	Output isn't correct
43	Incorrect	2 ms	9964 KB	Output isn't correct
44	Incorrect	116 ms	9964 KB	Output isn't correct
45	Incorrect	131 ms	9964 KB	Output isn't correct
46	Incorrect	59 ms	9964 KB	Output isn't correct
47	Incorrect	112 ms	9964 KB	Output isn't correct
48	Incorrect	120 ms	9964 KB	Output isn't correct
49	Incorrect	98 ms	9964 KB	Output isn't correct
50	Incorrect	114 ms	9964 KB	Output isn't correct
51	Incorrect	123 ms	9984 KB	Output isn't correct
52	Incorrect	117 ms	9984 KB	Output isn't correct
53	Incorrect	133 ms	9984 KB	Output isn't correct
54	Incorrect	122 ms	9984 KB	Output isn't correct
55	Incorrect	5 ms	9984 KB	Output isn't correct
56	Incorrect	5 ms	9984 KB	Output isn't correct
57	Incorrect	4 ms	9984 KB	Output isn't correct
58	Incorrect	4 ms	9984 KB	Output isn't correct
59	Incorrect	5 ms	9984 KB	Output isn't correct
60	Correct	5 ms	9984 KB	Output is correct
61	Incorrect	5 ms	9984 KB	Output isn't correct
62	Incorrect	3 ms	9984 KB	Output isn't correct
63	Incorrect	5 ms	9984 KB	Output isn't correct
64	Incorrect	4 ms	9984 KB	Output isn't correct
65	Incorrect	6 ms	9984 KB	Output isn't correct
66	Incorrect	7 ms	9984 KB	Output isn't correct
67	Incorrect	6 ms	9984 KB	Output isn't correct
68	Incorrect	5 ms	9984 KB	Output isn't correct
69	Incorrect	4 ms	9984 KB	Output isn't correct
70	Incorrect	4 ms	9984 KB	Output isn't correct
71	Incorrect	3 ms	9984 KB	Output isn't correct
72	Correct	6 ms	9984 KB	Output is correct
73	Incorrect	4 ms	9984 KB	Output isn't correct
74	Correct	6 ms	9984 KB	Output is correct
75	Incorrect	174 ms	9984 KB	Output isn't correct
76	Incorrect	105 ms	9984 KB	Output isn't correct
77	Incorrect	139 ms	9984 KB	Output isn't correct
78	Incorrect	113 ms	10028 KB	Output isn't correct
79	Correct	144 ms	10028 KB	Output is correct
80	Incorrect	169 ms	10028 KB	Output isn't correct
81	Incorrect	6 ms	10028 KB	Output isn't correct
82	Incorrect	146 ms	10028 KB	Output isn't correct
83	Incorrect	83 ms	10028 KB	Output isn't correct
84	Incorrect	136 ms	10028 KB	Output isn't correct
85	Incorrect	144 ms	10068 KB	Output isn't correct
86	Incorrect	140 ms	10068 KB	Output isn't correct
87	Incorrect	93 ms	10068 KB	Output isn't correct
88	Incorrect	91 ms	10068 KB	Output isn't correct
89	Incorrect	160 ms	10068 KB	Output isn't correct
90	Incorrect	165 ms	10068 KB	Output isn't correct
91	Incorrect	153 ms	10068 KB	Output isn't correct
92	Correct	131 ms	10068 KB	Output is correct
93	Incorrect	158 ms	10068 KB	Output isn't correct
94	Incorrect	162 ms	10068 KB	Output isn't correct
95	Incorrect	155 ms	10068 KB	Output isn't correct

답안 #66298

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