답안 #66297 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66297	2018-08-10T07:38:48 Z	정원준(#1889)	초음속철도 (OJUZ11_rail)	C++11	0 / 100	193 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;
	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]+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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Incorrect	3 ms	484 KB	Output isn't correct
4	Incorrect	2 ms	484 KB	Output isn't correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	516 KB	Output is correct
7	Incorrect	2 ms	644 KB	Output isn't correct
8	Incorrect	3 ms	644 KB	Output isn't correct
9	Correct	2 ms	644 KB	Output is correct
10	Incorrect	2 ms	644 KB	Output isn't correct
11	Correct	3 ms	644 KB	Output is correct
12	Incorrect	2 ms	644 KB	Output isn't correct
13	Correct	2 ms	644 KB	Output is correct
14	Correct	3 ms	644 KB	Output is correct
15	Incorrect	3 ms	644 KB	Output isn't correct
16	Incorrect	3 ms	644 KB	Output isn't correct
17	Correct	2 ms	644 KB	Output is correct
18	Correct	2 ms	644 KB	Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	644 KB	Output is correct
2	Correct	3 ms	644 KB	Output is correct
3	Correct	2 ms	748 KB	Output is correct
4	Incorrect	5 ms	876 KB	Output isn't correct
5	Incorrect	107 ms	9980 KB	Output isn't correct
6	Incorrect	110 ms	9988 KB	Output isn't correct
7	Incorrect	108 ms	9988 KB	Output isn't correct
8	Incorrect	2 ms	9988 KB	Output isn't correct
9	Incorrect	115 ms	9988 KB	Output isn't correct
10	Incorrect	118 ms	9988 KB	Output isn't correct
11	Incorrect	49 ms	9988 KB	Output isn't correct
12	Incorrect	113 ms	10000 KB	Output isn't correct
13	Incorrect	120 ms	10000 KB	Output isn't correct
14	Incorrect	73 ms	10000 KB	Output isn't correct
15	Correct	126 ms	10068 KB	Output is correct
16	Incorrect	80 ms	10068 KB	Output isn't correct
17	Incorrect	127 ms	10068 KB	Output isn't correct
18	Incorrect	114 ms	10068 KB	Output isn't correct
19	Incorrect	124 ms	10068 KB	Output isn't correct

Subtask #4
0 / 27.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Incorrect	3 ms	484 KB	Output isn't correct
4	Incorrect	2 ms	484 KB	Output isn't correct
5	Correct	2 ms	484 KB	Output is correct
6	Correct	2 ms	516 KB	Output is correct
7	Incorrect	2 ms	644 KB	Output isn't correct
8	Incorrect	3 ms	644 KB	Output isn't correct
9	Correct	2 ms	644 KB	Output is correct
10	Incorrect	2 ms	644 KB	Output isn't correct
11	Correct	3 ms	644 KB	Output is correct
12	Incorrect	2 ms	644 KB	Output isn't correct
13	Correct	2 ms	644 KB	Output is correct
14	Correct	3 ms	644 KB	Output is correct
15	Incorrect	3 ms	644 KB	Output isn't correct
16	Incorrect	3 ms	644 KB	Output isn't correct
17	Correct	2 ms	644 KB	Output is correct
18	Correct	2 ms	644 KB	Output is correct
19	Incorrect	3 ms	644 KB	Output isn't correct
20	Incorrect	2 ms	644 KB	Output isn't correct
21	Correct	2 ms	644 KB	Output is correct
22	Incorrect	3 ms	644 KB	Output isn't correct
23	Incorrect	3 ms	644 KB	Output isn't correct
24	Incorrect	3 ms	644 KB	Output isn't correct
25	Incorrect	2 ms	644 KB	Output isn't correct
26	Incorrect	3 ms	644 KB	Output isn't correct
27	Correct	2 ms	644 KB	Output is correct
28	Correct	2 ms	644 KB	Output is correct
29	Incorrect	2 ms	644 KB	Output isn't correct
30	Incorrect	3 ms	644 KB	Output isn't correct
31	Incorrect	3 ms	644 KB	Output isn't correct
32	Incorrect	2 ms	644 KB	Output isn't correct
33	Correct	3 ms	644 KB	Output is correct
34	Correct	3 ms	644 KB	Output is correct
35	Correct	3 ms	644 KB	Output is correct
36	Correct	2 ms	644 KB	Output is correct
37	Correct	3 ms	644 KB	Output is correct
38	Correct	2 ms	748 KB	Output is correct
39	Incorrect	5 ms	876 KB	Output isn't correct
40	Incorrect	107 ms	9980 KB	Output isn't correct
41	Incorrect	110 ms	9988 KB	Output isn't correct
42	Incorrect	108 ms	9988 KB	Output isn't correct
43	Incorrect	2 ms	9988 KB	Output isn't correct
44	Incorrect	115 ms	9988 KB	Output isn't correct
45	Incorrect	118 ms	9988 KB	Output isn't correct
46	Incorrect	49 ms	9988 KB	Output isn't correct
47	Incorrect	113 ms	10000 KB	Output isn't correct
48	Incorrect	120 ms	10000 KB	Output isn't correct
49	Incorrect	73 ms	10000 KB	Output isn't correct
50	Correct	126 ms	10068 KB	Output is correct
51	Incorrect	80 ms	10068 KB	Output isn't correct
52	Incorrect	127 ms	10068 KB	Output isn't correct
53	Incorrect	114 ms	10068 KB	Output isn't correct
54	Incorrect	124 ms	10068 KB	Output isn't correct
55	Incorrect	5 ms	10068 KB	Output isn't correct
56	Incorrect	5 ms	10068 KB	Output isn't correct
57	Incorrect	5 ms	10068 KB	Output isn't correct
58	Incorrect	4 ms	10068 KB	Output isn't correct
59	Correct	6 ms	10068 KB	Output is correct
60	Correct	7 ms	10068 KB	Output is correct
61	Incorrect	6 ms	10068 KB	Output isn't correct
62	Incorrect	2 ms	10068 KB	Output isn't correct
63	Incorrect	5 ms	10068 KB	Output isn't correct
64	Correct	4 ms	10068 KB	Output is correct
65	Incorrect	4 ms	10068 KB	Output isn't correct
66	Incorrect	5 ms	10068 KB	Output isn't correct
67	Incorrect	6 ms	10068 KB	Output isn't correct
68	Incorrect	5 ms	10068 KB	Output isn't correct
69	Incorrect	5 ms	10068 KB	Output isn't correct
70	Incorrect	4 ms	10068 KB	Output isn't correct
71	Incorrect	3 ms	10068 KB	Output isn't correct
72	Correct	5 ms	10068 KB	Output is correct
73	Incorrect	5 ms	10068 KB	Output isn't correct
74	Correct	6 ms	10068 KB	Output is correct
75	Incorrect	161 ms	10068 KB	Output isn't correct
76	Incorrect	96 ms	10068 KB	Output isn't correct
77	Incorrect	137 ms	10068 KB	Output isn't correct
78	Incorrect	60 ms	10068 KB	Output isn't correct
79	Correct	139 ms	10068 KB	Output is correct
80	Incorrect	158 ms	10068 KB	Output isn't correct
81	Incorrect	5 ms	10068 KB	Output isn't correct
82	Incorrect	141 ms	10068 KB	Output isn't correct
83	Correct	74 ms	10068 KB	Output is correct
84	Incorrect	148 ms	10068 KB	Output isn't correct
85	Incorrect	158 ms	10068 KB	Output isn't correct
86	Incorrect	140 ms	10068 KB	Output isn't correct
87	Incorrect	143 ms	10068 KB	Output isn't correct
88	Incorrect	101 ms	10068 KB	Output isn't correct
89	Incorrect	167 ms	10068 KB	Output isn't correct
90	Incorrect	166 ms	10068 KB	Output isn't correct
91	Incorrect	179 ms	10068 KB	Output isn't correct
92	Correct	148 ms	10068 KB	Output is correct
93	Incorrect	155 ms	10068 KB	Output isn't correct
94	Incorrect	193 ms	10068 KB	Output isn't correct
95	Incorrect	167 ms	10068 KB	Output isn't correct

답안 #66297

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