oj.uz

Submission #105007

# Submission time Handle Problem Language Result Execution time Memory
105007 2019-04-10T06:12:32 Z Just_Solve_The_Problem Bitaro, who Leaps through Time (JOI19_timeleap) C++11
4 / 100
 3000 ms 5772 KB 
#include <bits/stdc++.h>

#define ll long long
#define fr first
#define sc second

using namespace std;

const int N = (int)3e5 + 7;

int n, q;
pair < int, int > ar[2][N];

ll solve1(int a, int b, int c, int d) {
	ll res = 0;
	int cur = b - a;
	d -= c;
	for (int i = a + 1; i <= c; i++) {
		cur = max(cur, ar[0][i].fr);
		res += max(cur - ar[0][i].sc, 0);
		cur = min(cur, ar[0][i].sc);
	}
	res += max(cur - d, 0);
	return res;
}

ll solve2(int a, int b, int c, int d) {
	ll res = 0;
	int cur = b + a;
	d += c;
	for (int i = a; i > c; i--) {
		cur = max(cur, ar[1][i].fr);
		res += max(cur - ar[1][i].sc, 0);
		cur = min(cur, ar[1][i].sc);
	}
	res += max(cur - d, 0);
	return res;
}

main() {
	scanf("%d %d", &n, &q);
	for (int i = 2; i <= n; i++) {
		scanf("%d %d", &ar[0][i].fr, &ar[0][i].sc);
		ar[1][i].fr = ar[0][i].fr + i;
		ar[1][i].sc = ar[0][i].sc + i - 1;
		ar[0][i].fr = ar[0][i].fr - i + 1;
		ar[0][i].sc = ar[0][i].sc - i;
	}
	while (q--) {
		int tp;
		scanf("%d", &tp);
		if (tp == 1) {
			int i, l, r;
			scanf("%d %d %d", &i, &l, &r);
			i++;
			ar[1][i].fr = l + i;
			ar[1][i].sc = r + i - 1;
			ar[0][i].fr = l - i + 1;
			ar[0][i].sc = r - i;
		} else {
			int a, b, c, d;
			scanf("%d %d %d %d", &a, &b, &c, &d);
			ll ans;
			if (a < c) {
				ans = solve1(a, b, c, d);
			} else {
				ans = solve2(a, b, c, d);
			}
			printf("%lld\n", ans);
		}
	}
}

Compilation message

timeleap.cpp:40:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
timeleap.cpp: In function 'int main()':
timeleap.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &ar[0][i].fr, &ar[0][i].sc);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &tp);
   ~~~~~^~~~~~~~~~~
timeleap.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &i, &l, &r);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:62:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d %d", &a, &b, &c, &d);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 512 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 0 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 4 ms 380 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 4 ms 384 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 4 ms 384 KB Output is correct
33 Correct 4 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 4 ms 384 KB Output is correct
37 Correct 4 ms 384 KB Output is correct
38 Correct 4 ms 384 KB Output is correct
39 Correct 5 ms 384 KB Output is correct
40 Correct 4 ms 384 KB Output is correct
41 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3086 ms 5772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 512 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 0 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 4 ms 380 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 4 ms 384 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 4 ms 384 KB Output is correct
33 Correct 4 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 4 ms 384 KB Output is correct
37 Correct 4 ms 384 KB Output is correct
38 Correct 4 ms 384 KB Output is correct
39 Correct 5 ms 384 KB Output is correct
40 Correct 4 ms 384 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Execution timed out 3086 ms 5772 KB Time limit exceeded
43 Halted 0 ms 0 KB -