oj.uz

Submission #210356

# Submission time Handle Problem Language Result Execution time Memory
210356 2020-03-17T06:42:19 Z DrumpfTheGodEmperor Bitaro, who Leaps through Time (JOI19_timeleap) C++14
4 / 100
 3000 ms 15096 KB 
#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 3e5 + 5;
int n, q, l[N], r[N], l2[N], r2[N];
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	fw (i, 0, n - 1) {
		cin >> l[i] >> r[i];
		l2[n - 2 - i] = l[i], r2[n - 2 - i] = r[i];
	}
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int road, s, e;
			cin >> road >> s >> e;
			road--;
			l[road] = s, r[road] = e;
			l2[n - 2 - road] = s, r2[n - 2 - road] = e;
		} else {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			a--, c--;
			if (a == c) {
				if (b < d) cout << "0\n";
				else cout << b - d << "\n";
			} else if (a < c) {
				int ans = 0, cur = b - a;
				fw (i, a, c + 1) {
					int lval = l[i], rval = r[i];
					if (i == c) rval = d + 1;
					
					ans += max(0ll, cur + i - rval + 1);
					
					cur = min(cur, rval - i - 1);
					cur = max(cur, lval - i);
				}
				cout << ans << "\n";
			} else {
				a = n - 1 - a, c = n - 1 - c;
				assert(a < c);
				
				int ans = 0, cur = b - a;
				fw (i, a, c + 1) {
					int lval = l2[i], rval = r2[i];
					if (i == c) rval = d + 1;
					
					ans += max(0ll, cur + i - rval + 1);
					
					cur = min(cur, rval - i - 1);
					cur = max(cur, lval - i);
				}
				cout << ans << "\n";
			}
		}
	}
	return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 66.0

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