oj.uz

Submission #20390

# Submission time Handle Problem Language Result Execution time Memory
20390 2017-02-10T17:40:49 Z 윤지학(#34, gs13068) 초음속철도 (OJUZ11_rail) C++
0 / 100
 3 ms 29244 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

const int P = 1000000007;

pair<int, int> a[200002];
int t[400004];

struct tree {
	tree *l, *r;
	int s, e, x, y;
} T[800008];
int Tn;

void Init(tree *p, int s, int e) {
	p->s = s;
	p->e = e;
	p->x = s == 1 && e == 1;
	p->y = 1;
	if (s != e) {
		Init(p->l = T + ++Tn, s, s + e >> 1);
		Init(p->r = T + ++Tn, (s + e >> 1) + 1, e);
	}
}

void Lazy(tree *p) {
	p->l->x = ((long long)p->l->x * p->y + p->x) % P;
	p->l->y = (long long)p->l->y * p->y % P;
	p->r->x = ((long long)p->r->x * p->y + p->x) % P;
	p->r->y = (long long)p->r->y * p->y % P;
	p->y = 1;
	p->x = 0;
}

void Mul(tree *p, int e) {
	if (p->s > e) return;
	if (p->e == e) {
		p->x = (p->x << 1) % P;
		p->y = (p->y << 1) % P;
		return;
	}
	Lazy(p);
	Mul(p->l, e);
	Mul(p->r, e);
}

void Add(tree *p, int s, int e, int x) {
	if (p->s > e || p->e < s) return;
	if (s <= p->s && p->e <= e) {
		p->x = (p->x + x) % P;
		return;
	}
	Lazy(p);
	Add(p->l, s, e, x);
	Add(p->r, s, e, x);
}

int Get(tree *p, int x) {
	if (p->s == x && p->e == x) return p->x;
	Lazy(p);
	return p->r->s > x ? Get(p->l, x) : Get(p->r, x);
}

int main() {
	int i, j, k, n, m, r = 0;
	scanf("%d%d", &t[1], &n);
	if (n > 5000) return 0;
	t[0] = 1;
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &t[i << 1], &t[i << 1 | 1]);
		a[i].first = t[i << 1 | 1];
		a[i].second = -t[i << 1];
	}
	sort(a + 1, a + n + 1);
	sort(t, t + n + n + 2);
	m = unique(t, t + n + n + 2) - t;
	Init(T, 1, m);
	for (i = 1; i <= n; i++) {
		a[i].first = upper_bound(t, t + m, a[i].first) - t;
		a[i].second = upper_bound(t, t + m, -a[i].second) - t;
		k = Get(T, a[i].second);
		if (a[i].first == m) r = (r + k) % P;
		Mul(T, a[i].second - 1);
		Add(T, a[i].second, a[i].first, k);
	}
	printf("%d", r);
}

Compilation message

rail.cpp: In function 'void Init(tree*, int, int)':
rail.cpp:23:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   Init(p->l = T + ++Tn, s, s + e >> 1);
                              ^
rail.cpp:24:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   Init(p->r = T + ++Tn, (s + e >> 1) + 1, e);
                            ^
rail.cpp: In function 'int main()':
rail.cpp:67:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, n, m, r = 0;
         ^
rail.cpp:68:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &t[1], &n);
                          ^
rail.cpp:72:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &t[i << 1], &t[i << 1 | 1]);
                                            ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 29244 KB Output is correct
2 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 0 ms 29244 KB Output is correct
6 Correct 0 ms 29244 KB Output is correct
7 Correct 0 ms 29244 KB Output is correct
8 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 0 ms 29244 KB Output is correct
10 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 0 ms 29244 KB Output is correct
14 Correct 0 ms 29244 KB Output is correct
15 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 29244 KB Output is correct
2 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 0 ms 29244 KB Output is correct
6 Correct 0 ms 29244 KB Output is correct
7 Correct 0 ms 29244 KB Output is correct
8 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 0 ms 29244 KB Output is correct
10 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 0 ms 29244 KB Output is correct
14 Correct 0 ms 29244 KB Output is correct
15 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Correct 0 ms 29244 KB Output is correct
29 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 0 ms 29244 KB Output is correct
3 Correct 0 ms 29244 KB Output is correct
4 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 0 ms 29244 KB Output isn't correct
6 Incorrect 0 ms 29244 KB Output isn't correct
7 Incorrect 0 ms 29244 KB Output isn't correct
8 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 0 ms 29244 KB Output isn't correct
10 Incorrect 0 ms 29244 KB Output isn't correct
11 Incorrect 0 ms 29244 KB Output isn't correct
12 Incorrect 0 ms 29244 KB Output isn't correct
13 Incorrect 0 ms 29244 KB Output isn't correct
14 Incorrect 0 ms 29244 KB Output isn't correct
15 Incorrect 0 ms 29244 KB Output isn't correct
16 Incorrect 0 ms 29244 KB Output isn't correct
17 Incorrect 0 ms 29244 KB Output isn't correct
18 Incorrect 0 ms 29244 KB Output isn't correct
19 Incorrect 0 ms 29244 KB Output isn't correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 29244 KB Output is correct
2 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 0 ms 29244 KB Output is correct
6 Correct 0 ms 29244 KB Output is correct
7 Correct 0 ms 29244 KB Output is correct
8 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 0 ms 29244 KB Output is correct
10 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 0 ms 29244 KB Output is correct
14 Correct 0 ms 29244 KB Output is correct
15 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Correct 0 ms 29244 KB Output is correct
29 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Correct 3 ms 29244 KB Output is correct
40 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Correct 0 ms 29244 KB Output is correct
46 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 29244 KB Output is correct
2 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 0 ms 29244 KB Output is correct
6 Correct 0 ms 29244 KB Output is correct
7 Correct 0 ms 29244 KB Output is correct
8 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 0 ms 29244 KB Output is correct
10 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 0 ms 29244 KB Output is correct
14 Correct 0 ms 29244 KB Output is correct
15 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Correct 0 ms 29244 KB Output is correct
29 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Correct 0 ms 29244 KB Output is correct
38 Correct 0 ms 29244 KB Output is correct
39 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Incorrect 0 ms 29244 KB Output isn't correct
41 Incorrect 0 ms 29244 KB Output isn't correct
42 Incorrect 0 ms 29244 KB Output isn't correct
43 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Incorrect 0 ms 29244 KB Output isn't correct
45 Incorrect 0 ms 29244 KB Output isn't correct
46 Incorrect 0 ms 29244 KB Output isn't correct
47 Incorrect 0 ms 29244 KB Output isn't correct
48 Incorrect 0 ms 29244 KB Output isn't correct
49 Incorrect 0 ms 29244 KB Output isn't correct
50 Incorrect 0 ms 29244 KB Output isn't correct
51 Incorrect 0 ms 29244 KB Output isn't correct
52 Incorrect 0 ms 29244 KB Output isn't correct
53 Incorrect 0 ms 29244 KB Output isn't correct
54 Incorrect 0 ms 29244 KB Output isn't correct
55 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
57 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Correct 3 ms 29244 KB Output is correct
59 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
63 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Correct 0 ms 29244 KB Output is correct
65 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
69 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
71 Runtime error 0 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Runtime error 3 ms 29244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Incorrect 0 ms 29244 KB Output isn't correct
76 Incorrect 0 ms 29244 KB Output isn't correct
77 Incorrect 0 ms 29244 KB Output isn't correct
78 Incorrect 0 ms 29244 KB Output isn't correct
79 Incorrect 0 ms 29244 KB Output isn't correct
80 Incorrect 0 ms 29244 KB Output isn't correct
81 Incorrect 0 ms 29244 KB Output isn't correct
82 Incorrect 0 ms 29244 KB Output isn't correct
83 Incorrect 0 ms 29244 KB Output isn't correct
84 Incorrect 0 ms 29244 KB Output isn't correct
85 Incorrect 0 ms 29244 KB Output isn't correct
86 Incorrect 0 ms 29244 KB Output isn't correct
87 Incorrect 0 ms 29244 KB Output isn't correct
88 Incorrect 0 ms 29244 KB Output isn't correct
89 Incorrect 0 ms 29244 KB Output isn't correct
90 Incorrect 0 ms 29244 KB Output isn't correct
91 Incorrect 0 ms 29244 KB Output isn't correct
92 Incorrect 0 ms 29244 KB Output isn't correct
93 Incorrect 0 ms 29244 KB Output isn't correct
94 Incorrect 0 ms 29244 KB Output isn't correct
95 Incorrect 0 ms 29244 KB Output isn't correct