답안 #20466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20466 2017-02-12T00:55:38 Z 책상다리황새두렁넘기(#60, khsoo01) 초음속철도 (OJUZ11_rail) C++11
45 / 100
9 ms 18552 KB
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

ll m, n, two[100005], sz;
pair<ll,ll> a[100005];
vector<ll> cpr;

struct segtree {
	ll val[888888], lazy[888888];
	void lazydown (ll P) {
		val[2*P] = (val[2*P] * two[lazy[P]]) % mod;
		lazy[2*P] += lazy[P];
		val[2*P+1] = (val[2*P+1] * two[lazy[P]]) % mod;
		lazy[2*P+1] += lazy[P];
		lazy[P] = 0;
	}
	void pl (ll SS, ll SE, ll X, ll P, ll V) {
		if(SE < X || X < SS) return;
		if(SS == SE) {val[P] += V; return;}
		lazydown(P);
		ll mid = (SS+SE)/2;
		pl(SS, mid, X, 2*P, V);
		pl(mid+1, SE, X, 2*P+1, V);
		val[P] = (val[2*P] + val[2*P+1]) % mod;
	}
	void pl(ll X, ll V) {pl(0, sz-1, X, 1, V);}
	void ml (ll SS, ll SE, ll S, ll E, ll P, ll V) {
		if(S <= SS && SE <= E) {
			val[P] = (val[P] * two[V]) % mod;
			lazy[P] += V;
			return;
		}
		if(SE < S || E < SS) return;
		lazydown(P);
		ll mid = (SS+SE)/2;
		ml(SS, mid, S, E, 2*P, V);
		ml(mid+1, SE, S, E, 2*P+1, V);
		val[P] = (val[2*P] + val[2*P+1]) % mod;
	}
	void ml (ll S, ll E, ll V) {ml(0, sz-1, S, E, 1, V);}
	ll query (ll SS, ll SE, ll S, ll E, ll P) {
		if(S <= SS && SE <= E) return val[P];
		if(SE < S || E < SS) return 0;
		lazydown(P);
		ll mid = (SS+SE)/2;
		return (query(SS, mid, S, E, 2*P) +
				query(mid+1, SE, S, E, 2*P+1)) % mod;
	}
	ll query (ll S, ll E) {return query(0, sz-1, S, E, 1);}
} seg;

int main()
{
	scanf("%lld%lld",&m,&n);
	two[0] = 1;
	for(int i=1;i<=n;i++) {
		two[i] = (two[i-1] * 2) % mod;
	}
	for(int i=1;i<=n;i++) {
		scanf("%lld%lld",&a[i].X,&a[i].Y);
		cpr.push_back(a[i].X);
		cpr.push_back(a[i].Y);
	}
	sort(cpr.begin(), cpr.end());
	cpr.erase(unique(cpr.begin(), cpr.end()), cpr.end());
	if(cpr[0] != 1 || cpr.back() != m) {puts("0"); return 0;}
	for(int i=1;i<=n;i++) {
		a[i].X = lower_bound(cpr.begin(), cpr.end(), a[i].X) - cpr.begin();
		a[i].Y = lower_bound(cpr.begin(), cpr.end(), a[i].Y) - cpr.begin();
	}
	sort(a+1, a+1+n);
	sz = cpr.size();
	seg.pl(0, 1);
	for(int i=1;i<=n;i++) {
		seg.pl(a[i].Y, seg.query(a[i].X, a[i].Y));
		seg.ml(a[i].Y+1, sz-1, 1);
	}
	printf("%lld\n",seg.query(sz-1, sz-1));
}

Compilation message

rail.cpp: In function 'int main()':
rail.cpp:58:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&m,&n);
                         ^
rail.cpp:64:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a[i].X,&a[i].Y);
                                    ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 18280 KB Output is correct
2 Correct 0 ms 18280 KB Output is correct
3 Correct 0 ms 18280 KB Output is correct
4 Correct 0 ms 18280 KB Output is correct
5 Correct 0 ms 18280 KB Output is correct
6 Correct 0 ms 18280 KB Output is correct
7 Correct 0 ms 18280 KB Output is correct
8 Correct 0 ms 18280 KB Output is correct
9 Correct 0 ms 18280 KB Output is correct
10 Correct 0 ms 18280 KB Output is correct
11 Correct 0 ms 18280 KB Output is correct
12 Correct 0 ms 18280 KB Output is correct
13 Correct 0 ms 18280 KB Output is correct
14 Correct 0 ms 18280 KB Output is correct
15 Correct 0 ms 18280 KB Output is correct
16 Correct 0 ms 18280 KB Output is correct
17 Correct 0 ms 18280 KB Output is correct
18 Correct 0 ms 18280 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 18280 KB Output is correct
2 Correct 0 ms 18280 KB Output is correct
3 Correct 0 ms 18280 KB Output is correct
4 Correct 0 ms 18280 KB Output is correct
5 Correct 0 ms 18280 KB Output is correct
6 Correct 0 ms 18280 KB Output is correct
7 Correct 0 ms 18280 KB Output is correct
8 Correct 0 ms 18280 KB Output is correct
9 Correct 0 ms 18280 KB Output is correct
10 Correct 0 ms 18280 KB Output is correct
11 Correct 0 ms 18280 KB Output is correct
12 Correct 0 ms 18280 KB Output is correct
13 Correct 0 ms 18280 KB Output is correct
14 Correct 0 ms 18280 KB Output is correct
15 Correct 0 ms 18280 KB Output is correct
16 Correct 0 ms 18280 KB Output is correct
17 Correct 0 ms 18280 KB Output is correct
18 Correct 0 ms 18280 KB Output is correct
19 Correct 0 ms 18280 KB Output is correct
20 Correct 0 ms 18280 KB Output is correct
21 Correct 0 ms 18280 KB Output is correct
22 Correct 0 ms 18280 KB Output is correct
23 Correct 0 ms 18280 KB Output is correct
24 Correct 0 ms 18280 KB Output is correct
25 Correct 0 ms 18280 KB Output is correct
26 Correct 0 ms 18280 KB Output is correct
27 Correct 0 ms 18280 KB Output is correct
28 Correct 0 ms 18280 KB Output is correct
29 Correct 0 ms 18280 KB Output is correct
30 Correct 0 ms 18280 KB Output is correct
31 Correct 0 ms 18280 KB Output is correct
32 Correct 0 ms 18280 KB Output is correct
33 Correct 0 ms 18280 KB Output is correct
34 Correct 0 ms 18280 KB Output is correct
35 Correct 0 ms 18280 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 18280 KB Output is correct
2 Correct 0 ms 18280 KB Output is correct
3 Correct 0 ms 18280 KB Output is correct
4 Correct 3 ms 18552 KB Output is correct
5 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 0 ms 18280 KB Output is correct
9 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 18280 KB Output is correct
2 Correct 0 ms 18280 KB Output is correct
3 Correct 0 ms 18280 KB Output is correct
4 Correct 0 ms 18280 KB Output is correct
5 Correct 0 ms 18280 KB Output is correct
6 Correct 0 ms 18280 KB Output is correct
7 Correct 0 ms 18280 KB Output is correct
8 Correct 0 ms 18280 KB Output is correct
9 Correct 0 ms 18280 KB Output is correct
10 Correct 0 ms 18280 KB Output is correct
11 Correct 0 ms 18280 KB Output is correct
12 Correct 0 ms 18280 KB Output is correct
13 Correct 0 ms 18280 KB Output is correct
14 Correct 0 ms 18280 KB Output is correct
15 Correct 0 ms 18280 KB Output is correct
16 Correct 0 ms 18280 KB Output is correct
17 Correct 0 ms 18280 KB Output is correct
18 Correct 0 ms 18280 KB Output is correct
19 Correct 0 ms 18280 KB Output is correct
20 Correct 0 ms 18280 KB Output is correct
21 Correct 0 ms 18280 KB Output is correct
22 Correct 0 ms 18280 KB Output is correct
23 Correct 0 ms 18280 KB Output is correct
24 Correct 0 ms 18280 KB Output is correct
25 Correct 0 ms 18280 KB Output is correct
26 Correct 0 ms 18280 KB Output is correct
27 Correct 0 ms 18280 KB Output is correct
28 Correct 0 ms 18280 KB Output is correct
29 Correct 0 ms 18280 KB Output is correct
30 Correct 0 ms 18280 KB Output is correct
31 Correct 0 ms 18280 KB Output is correct
32 Correct 0 ms 18280 KB Output is correct
33 Correct 0 ms 18280 KB Output is correct
34 Correct 0 ms 18280 KB Output is correct
35 Correct 0 ms 18280 KB Output is correct
36 Correct 6 ms 18552 KB Output is correct
37 Correct 6 ms 18420 KB Output is correct
38 Correct 6 ms 18420 KB Output is correct
39 Correct 0 ms 18552 KB Output is correct
40 Correct 6 ms 18552 KB Output is correct
41 Correct 0 ms 18552 KB Output is correct
42 Correct 9 ms 18552 KB Output is correct
43 Correct 0 ms 18280 KB Output is correct
44 Correct 3 ms 18552 KB Output is correct
45 Correct 0 ms 18552 KB Output is correct
46 Correct 3 ms 18552 KB Output is correct
47 Correct 6 ms 18552 KB Output is correct
48 Correct 6 ms 18552 KB Output is correct
49 Correct 3 ms 18552 KB Output is correct
50 Correct 3 ms 18552 KB Output is correct
51 Correct 3 ms 18552 KB Output is correct
52 Correct 0 ms 18280 KB Output is correct
53 Correct 0 ms 18552 KB Output is correct
54 Correct 3 ms 18420 KB Output is correct
55 Correct 3 ms 18552 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 18280 KB Output is correct
2 Correct 0 ms 18280 KB Output is correct
3 Correct 0 ms 18280 KB Output is correct
4 Correct 0 ms 18280 KB Output is correct
5 Correct 0 ms 18280 KB Output is correct
6 Correct 0 ms 18280 KB Output is correct
7 Correct 0 ms 18280 KB Output is correct
8 Correct 0 ms 18280 KB Output is correct
9 Correct 0 ms 18280 KB Output is correct
10 Correct 0 ms 18280 KB Output is correct
11 Correct 0 ms 18280 KB Output is correct
12 Correct 0 ms 18280 KB Output is correct
13 Correct 0 ms 18280 KB Output is correct
14 Correct 0 ms 18280 KB Output is correct
15 Correct 0 ms 18280 KB Output is correct
16 Correct 0 ms 18280 KB Output is correct
17 Correct 0 ms 18280 KB Output is correct
18 Correct 0 ms 18280 KB Output is correct
19 Correct 0 ms 18280 KB Output is correct
20 Correct 0 ms 18280 KB Output is correct
21 Correct 0 ms 18280 KB Output is correct
22 Correct 0 ms 18280 KB Output is correct
23 Correct 0 ms 18280 KB Output is correct
24 Correct 0 ms 18280 KB Output is correct
25 Correct 0 ms 18280 KB Output is correct
26 Correct 0 ms 18280 KB Output is correct
27 Correct 0 ms 18280 KB Output is correct
28 Correct 0 ms 18280 KB Output is correct
29 Correct 0 ms 18280 KB Output is correct
30 Correct 0 ms 18280 KB Output is correct
31 Correct 0 ms 18280 KB Output is correct
32 Correct 0 ms 18280 KB Output is correct
33 Correct 0 ms 18280 KB Output is correct
34 Correct 0 ms 18280 KB Output is correct
35 Correct 0 ms 18280 KB Output is correct
36 Correct 0 ms 18280 KB Output is correct
37 Correct 0 ms 18280 KB Output is correct
38 Correct 0 ms 18280 KB Output is correct
39 Correct 3 ms 18552 KB Output is correct
40 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Correct 0 ms 18280 KB Output is correct
44 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Correct 6 ms 18552 KB Output is correct
56 Correct 6 ms 18420 KB Output is correct
57 Correct 6 ms 18420 KB Output is correct
58 Correct 0 ms 18552 KB Output is correct
59 Correct 6 ms 18552 KB Output is correct
60 Correct 0 ms 18552 KB Output is correct
61 Correct 9 ms 18552 KB Output is correct
62 Correct 0 ms 18280 KB Output is correct
63 Correct 3 ms 18552 KB Output is correct
64 Correct 0 ms 18552 KB Output is correct
65 Correct 3 ms 18552 KB Output is correct
66 Correct 6 ms 18552 KB Output is correct
67 Correct 6 ms 18552 KB Output is correct
68 Correct 3 ms 18552 KB Output is correct
69 Correct 3 ms 18552 KB Output is correct
70 Correct 3 ms 18552 KB Output is correct
71 Correct 0 ms 18280 KB Output is correct
72 Correct 0 ms 18552 KB Output is correct
73 Correct 3 ms 18420 KB Output is correct
74 Correct 3 ms 18552 KB Output is correct
75 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
79 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
80 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
81 Correct 6 ms 18552 KB Output is correct
82 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
83 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
90 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
91 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
92 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
93 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
94 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
95 Runtime error 0 ms 18280 KB Execution killed with signal 11 (could be triggered by violating memory limits)