답안 #20663 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20663	2017-02-13T11:46:10 Z	우리OJ(#80, cki86201)	초음속철도 (OJUZ11_rail)	C++14	0 / 100	709 ms	21532 KB

rail

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;

int n, m;
int xs[400040], xz;
Pi p[200020];

const int MOD = 1e9 + 7;

struct node{
	node(){sum = 0, C = 1;}
	ll sum, C;
}T[1<<20];

void add(int rt, int l, int r, int x, ll v){
	if(l == r){
		T[rt].sum = (T[rt].sum + v) % MOD;
		return;
	}
	if(T[rt].C != 1){
		T[rt<<1].C = (T[rt<<1].C * T[rt].C) % MOD;
		T[rt<<1|1].C = (T[rt<<1|1].C * T[rt].C) % MOD;
		T[rt<<1].sum = (T[rt<<1].sum * T[rt].C) % MOD;
		T[rt<<1|1].sum = (T[rt<<1|1].sum * T[rt].C) % MOD;
		T[rt].C = 1;
	}
	int m = (l + r) >> 1;
	if(x <= m)add(rt<<1, l, m, x, v);
	else add(rt<<1|1, m+1, r, x, v);
	T[rt].sum = (T[rt<<1].sum + T[rt<<1|1].sum) % MOD;
}

ll get_sum(int rt, int l,int r, int s, int d){
	if(s <= l && r <= d){
		return T[rt].sum;
	}
	if(T[rt].C != 1){
		T[rt<<1].C = (T[rt<<1].C * T[rt].C) % MOD;
		T[rt<<1|1].C = (T[rt<<1|1].C * T[rt].C) % MOD;
		T[rt<<1].sum = (T[rt<<1].sum * T[rt].C) % MOD;
		T[rt<<1|1].sum = (T[rt<<1|1].sum * T[rt].C) % MOD;
		T[rt].C = 1;
	}
	int m = (l + r) >> 1;
	ll res = 0;
	if(s <= m)res += get_sum(rt<<1, l, m, s, d);
	if(m < d)res += get_sum(rt<<1|1, m+1, r, s, d);
	return res % MOD;
}

void mul2(int rt, int l, int r, int s, int d){
	if(s <= l && r <= d){
		T[rt].sum = (T[rt].sum + T[rt].sum) % MOD;
		T[rt].C = (T[rt].C + T[rt].C) % MOD;
		return;
	}
	if(T[rt].C != 1){
		T[rt<<1].C = (T[rt<<1].C * T[rt].C) % MOD;
		T[rt<<1|1].C = (T[rt<<1|1].C * T[rt].C) % MOD;
		T[rt<<1].sum = (T[rt<<1].sum * T[rt].C) % MOD;
		T[rt<<1|1].sum = (T[rt<<1|1].sum * T[rt].C) % MOD;
		T[rt].C = 1;
	}
	int m = (l + r) >> 1;
	if(s <= m)mul2(rt<<1, l, m, s, d);
	if(m < d)mul2(rt<<1|1, m+1, r, s, d);
	T[rt].sum = (T[rt<<1].sum + T[rt<<1|1].sum) % MOD;
}

void solve(){
	scanf("%d%d", &n, &m);
	for(int i=1;i<=m;i++){
		int s, e;
		scanf("%d%d", &s, &e);
		p[i] = Pi(s, e);
		xs[xz++] = s, xs[xz++] = e;
	}
	xs[xz++] = 1; xs[xz++] = n;
	sort(xs, xs + xz);
	xz = (int)(unique(xs, xs + xz) - xs);
	for(int i=1;i<=m;i++){
		p[i].Fi = (int)(lower_bound(xs, xs + xz, p[i].Fi) - xs) + 1;
		p[i].Se = (int)(lower_bound(xs, xs + xz, p[i].Se) - xs) + 1;
	}
	add(1, 1, xz, 1, 1);
	for(int i=1;i<=m;i++){
		int l = p[i].Fi, r = p[i].Se;
		if(l != 1)mul2(1, 1, xz, 1, l-1);
		if(r != xz)mul2(1, 1, xz, r+1, xz);
		ll s = get_sum(1, 1, xz, l, r);
		add(1, 1, xz, r, s);
	}
	printf("%lld\n", get_sum(1, 1, xz, xz, xz));
}

int main(){
	int Tc = 1; //scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}

Compilation message

rail.cpp: In function 'void solve()':
rail.cpp:100:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
rail.cpp:103:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &e);
                        ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	21532 KB	Output is correct
2	Correct	0 ms	21532 KB	Output is correct
3	Correct	3 ms	21532 KB	Output is correct
4	Incorrect	6 ms	21532 KB	Output isn't correct
5	Incorrect	296 ms	21532 KB	Output isn't correct
6	Correct	533 ms	21532 KB	Output is correct
7	Correct	566 ms	21532 KB	Output is correct
8	Correct	6 ms	21532 KB	Output is correct
9	Correct	516 ms	21532 KB	Output is correct
10	Correct	533 ms	21532 KB	Output is correct
11	Correct	163 ms	21532 KB	Output is correct
12	Correct	563 ms	21532 KB	Output is correct
13	Correct	536 ms	21532 KB	Output is correct
14	Correct	73 ms	21532 KB	Output is correct
15	Incorrect	513 ms	21532 KB	Output isn't correct
16	Correct	76 ms	21532 KB	Output is correct
17	Correct	566 ms	21532 KB	Output is correct
18	Correct	576 ms	21532 KB	Output is correct
19	Correct	579 ms	21532 KB	Output is correct

Subtask #4
0 / 27.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	21532 KB	Output is correct
2	Incorrect	0 ms	21532 KB	Output isn't correct
3	Incorrect	0 ms	21532 KB	Output isn't correct
4	Incorrect	0 ms	21532 KB	Output isn't correct
5	Correct	9 ms	21532 KB	Output is correct
6	Correct	0 ms	21532 KB	Output is correct
7	Incorrect	0 ms	21532 KB	Output isn't correct
8	Incorrect	0 ms	21532 KB	Output isn't correct
9	Correct	0 ms	21532 KB	Output is correct
10	Incorrect	0 ms	21532 KB	Output isn't correct
11	Incorrect	3 ms	21532 KB	Output isn't correct
12	Incorrect	0 ms	21532 KB	Output isn't correct
13	Correct	0 ms	21532 KB	Output is correct
14	Correct	0 ms	21532 KB	Output is correct
15	Incorrect	0 ms	21532 KB	Output isn't correct
16	Incorrect	3 ms	21532 KB	Output isn't correct
17	Correct	3 ms	21532 KB	Output is correct
18	Correct	3 ms	21532 KB	Output is correct
19	Incorrect	0 ms	21532 KB	Output isn't correct
20	Incorrect	0 ms	21532 KB	Output isn't correct
21	Incorrect	0 ms	21532 KB	Output isn't correct
22	Incorrect	3 ms	21532 KB	Output isn't correct
23	Incorrect	0 ms	21532 KB	Output isn't correct
24	Incorrect	0 ms	21532 KB	Output isn't correct
25	Incorrect	0 ms	21532 KB	Output isn't correct
26	Incorrect	0 ms	21532 KB	Output isn't correct
27	Correct	6 ms	21532 KB	Output is correct
28	Correct	3 ms	21532 KB	Output is correct
29	Incorrect	0 ms	21532 KB	Output isn't correct
30	Incorrect	0 ms	21532 KB	Output isn't correct
31	Incorrect	6 ms	21532 KB	Output isn't correct
32	Incorrect	6 ms	21532 KB	Output isn't correct
33	Correct	3 ms	21532 KB	Output is correct
34	Correct	0 ms	21532 KB	Output is correct
35	Correct	0 ms	21532 KB	Output is correct
36	Correct	3 ms	21532 KB	Output is correct
37	Correct	0 ms	21532 KB	Output is correct
38	Correct	3 ms	21532 KB	Output is correct
39	Incorrect	6 ms	21532 KB	Output isn't correct
40	Incorrect	296 ms	21532 KB	Output isn't correct
41	Correct	533 ms	21532 KB	Output is correct
42	Correct	566 ms	21532 KB	Output is correct
43	Correct	6 ms	21532 KB	Output is correct
44	Correct	516 ms	21532 KB	Output is correct
45	Correct	533 ms	21532 KB	Output is correct
46	Correct	163 ms	21532 KB	Output is correct
47	Correct	563 ms	21532 KB	Output is correct
48	Correct	536 ms	21532 KB	Output is correct
49	Correct	73 ms	21532 KB	Output is correct
50	Incorrect	513 ms	21532 KB	Output isn't correct
51	Correct	76 ms	21532 KB	Output is correct
52	Correct	566 ms	21532 KB	Output is correct
53	Correct	576 ms	21532 KB	Output is correct
54	Correct	579 ms	21532 KB	Output is correct
55	Incorrect	9 ms	21532 KB	Output isn't correct
56	Incorrect	9 ms	21532 KB	Output isn't correct
57	Incorrect	13 ms	21532 KB	Output isn't correct
58	Incorrect	3 ms	21532 KB	Output isn't correct
59	Incorrect	6 ms	21532 KB	Output isn't correct
60	Correct	6 ms	21532 KB	Output is correct
61	Incorrect	13 ms	21532 KB	Output isn't correct
62	Incorrect	3 ms	21532 KB	Output isn't correct
63	Incorrect	6 ms	21532 KB	Output isn't correct
64	Correct	3 ms	21532 KB	Output is correct
65	Incorrect	9 ms	21532 KB	Output isn't correct
66	Incorrect	6 ms	21532 KB	Output isn't correct
67	Incorrect	9 ms	21532 KB	Output isn't correct
68	Incorrect	0 ms	21532 KB	Output isn't correct
69	Incorrect	3 ms	21532 KB	Output isn't correct
70	Incorrect	6 ms	21532 KB	Output isn't correct
71	Incorrect	0 ms	21532 KB	Output isn't correct
72	Correct	13 ms	21532 KB	Output is correct
73	Incorrect	3 ms	21532 KB	Output isn't correct
74	Correct	13 ms	21532 KB	Output is correct
75	Incorrect	683 ms	21532 KB	Output isn't correct
76	Incorrect	406 ms	21532 KB	Output isn't correct
77	Incorrect	293 ms	21532 KB	Output isn't correct
78	Incorrect	63 ms	21532 KB	Output isn't correct
79	Correct	473 ms	21532 KB	Output is correct
80	Correct	709 ms	21532 KB	Output is correct
81	Incorrect	19 ms	21532 KB	Output isn't correct
82	Incorrect	623 ms	21532 KB	Output isn't correct
83	Correct	66 ms	21532 KB	Output is correct
84	Incorrect	549 ms	21532 KB	Output isn't correct
85	Incorrect	616 ms	21532 KB	Output isn't correct
86	Incorrect	623 ms	21532 KB	Output isn't correct
87	Incorrect	133 ms	21532 KB	Output isn't correct
88	Incorrect	139 ms	21532 KB	Output isn't correct
89	Incorrect	689 ms	21532 KB	Output isn't correct
90	Incorrect	706 ms	21532 KB	Output isn't correct
91	Incorrect	679 ms	21532 KB	Output isn't correct
92	Correct	673 ms	21532 KB	Output is correct
93	Incorrect	633 ms	21532 KB	Output isn't correct
94	Incorrect	709 ms	21532 KB	Output isn't correct
95	Incorrect	699 ms	21532 KB	Output isn't correct

답안 #20663

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