oj.uz

Submission #616237

# Submission time Handle Problem Language Result Execution time Memory
616237 2022-08-01T03:50:55 Z cheissmart Fish 2 (JOI22_fish2) C++14
60 / 100
 4000 ms 368964 KB 
// 花啊啊啊啊啊啊啊啊啊啊啊啊
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7;
const ll oo = 1e18;

ll a[N];
int n;

namespace cover {
	pi t[N * 4];
	int lz[N * 4];

	pi add(pi a, pi b) {
		if(a.F != b.F) return min(a, b);
		a.S += b.S;
		return a;
	}
	void apply(int v, int x) {
		t[v].F += x;
		lz[v] += x;
	}
	void push(int v) {
		apply(v * 2, lz[v]);
		apply(v * 2 + 1, lz[v]);
		lz[v] = 0;
	}
	void build(int v = 1, int tl = 1, int tr = n + 1) {
		if(tr - tl == 1) {
			t[v] = {0, 1};
			return;
		}
		int tm = (tl + tr) / 2;
		build(v * 2, tl, tm);
		build(v * 2 + 1, tm, tr);
		t[v] = add(t[v * 2], t[v * 2 + 1]);
	}
	void add(int l, int r, int x, int v = 1, int tl = 1, int tr = n + 1) {
		if(l <= tl && tr <= r) {
			apply(v, x);
			return;
		}
		push(v);
		int tm = (tl + tr) / 2;
		if(l < tm) add(l, r, x, v * 2, tl, tm);
		if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
		t[v] = add(t[v * 2], t[v * 2 + 1]);
	}
	pi qry(int l, int r, int v = 1, int tl = 1, int tr = n + 1) {
		if(l <= tl && tr <= r)
			return t[v];
		push(v);
		int tm = (tl + tr) / 2;
		pi res = {100, 100};
		if(l < tm) res = add(res, qry(l, r, v * 2, tl, tm));
		if(r > tm) res = add(res, qry(l, r, v * 2 + 1, tm, tr));
		return res;
	}
}

namespace seg {
	struct node {
		V<pair<int, ll>> bad_pref, bad_suff;
		V<pi> bad_seg;
		node() {
			bad_pref.reserve(20);
			bad_suff.reserve(20);
			bad_seg.reserve(20);
		}
		ll sum;
	} t[N * 4];
	void pull(int v, int posl = INF, int posr = 0) {
		t[v].bad_pref = t[v * 2].bad_pref;
		t[v].bad_suff = t[v * 2 + 1].bad_suff;

		for(auto[pos, sum]:t[v * 2 + 1].bad_pref) if(sum + t[v * 2].sum < a[pos + 1])
			t[v].bad_pref.EB(pos, sum + t[v * 2].sum);
		for(auto[pos, sum]:t[v * 2].bad_suff) if(sum + t[v * 2 + 1].sum < a[pos - 1])
			t[v].bad_suff.EB(pos, sum + t[v * 2 + 1].sum);

		int szi = SZ(t[v * 2].bad_suff);
		int szj = SZ(t[v * 2 + 1].bad_pref);
		int i = 0, j = 0;
		while(i < szi && t[v * 2].bad_suff[i].F > posl)
			i++;
		while(j < szj && t[v * 2 + 1].bad_pref[j].F < posr)
			j++;
		while(i < szi && j < szj) {
			auto he = t[v * 2].bad_suff[i], be = t[v * 2 + 1].bad_pref[j];
			if(he.S + be.S < min(a[he.F - 1], a[be.F + 1])) {
				t[v].bad_seg.EB(he.F, be.F);
				cover::add(he.F, be.F + 1, 1);
			}
			if(a[he.F - 1] < a[be.F + 1])
				i++;
			else
				j++;
		}
		t[v].sum = t[v * 2].sum + t[v * 2 + 1].sum;
	}
	void build(int v = 1, int tl = 1, int tr = n + 1) {
		if(tr - tl == 1) {
			t[v].sum = a[tl];
			if(a[tl] < a[tl + 1])
				t[v].bad_pref.EB(tl, a[tl]);
			if(a[tl] < a[tl - 1])
				t[v].bad_suff.EB(tl, a[tl]);
			if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1]) {
				t[v].bad_seg.EB(tl, tl);
				cover::add(tl, tl + 1, 1);
			}
		} else {
			int tm = (tl + tr) / 2;
			build(v * 2, tl, tm);
			build(v * 2 + 1, tm, tr);
			pull(v);
		}
	}
	void upd(int pos, int v = 1, int tl = 1, int tr = n + 1) {
		V<pi> tt;
		for(auto[l, r]:t[v].bad_seg) {
			if(r < pos - 1 || l > pos + 1) {
				tt.EB(l, r);
				continue;
			}
			cover::add(l, r + 1, -1);
		}
		t[v].bad_seg = tt, t[v].bad_pref.clear(), t[v].bad_suff.clear();

		if(tr - tl == 1) {
			t[v].sum = a[tl];
			if(a[tl] < a[tl + 1])
				t[v].bad_pref.EB(tl, a[tl]);
			if(a[tl] < a[tl - 1])
				t[v].bad_suff.EB(tl, a[tl]);
			if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1]) {
				t[v].bad_seg.EB(tl, tl);
				cover::add(tl, tl + 1, 1);
			}
		} else {
			int tm = (tl + tr) / 2;
			if(pos - 1 < tm)
				upd(pos, v * 2, tl, tm);
			if(pos + 1 >= tm)
				upd(pos, v * 2 + 1, tm, tr);
			pull(v, pos + 1, pos - 1);
		}
	}
}

void upd(int pos, ll val) {
	a[pos] = val;
	seg::upd(pos);
}

signed main()
{
	IO_OP;

	cin >> n;
	a[0] = a[n + 1] = oo;
	for(int i = 1; i <= n; i++)
		cin >> a[i];

	cover::build();
	seg::build();

	int q;
	cin >> q;
	while(q--) {
		int op;
		cin >> op;
		if(op == 1) {
			int x, y;
			cin >> x >> y;
			upd(x, y);
		} else {
			int l, r;
			cin >> l >> r;
			ll tl = a[l - 1], tr = a[r + 1];
			if(l - 1 >= 1) upd(l - 1, 1e15);
			if(r + 1 <= n) upd(r + 1, 1e15);

			auto p = cover::qry(l, r + 1);
			cout << p.S << '\n';

			if(l - 1 >= 1) upd(l - 1, tl);
			if(r + 1 <= n) upd(r + 1, tr);
		}
	}

}

Compilation message

fish2.cpp: In function 'void seg::pull(int, int, int)':
fish2.cpp:92:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |   for(auto[pos, sum]:t[v * 2 + 1].bad_pref) if(sum + t[v * 2].sum < a[pos + 1])
      |           ^
fish2.cpp:94:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |   for(auto[pos, sum]:t[v * 2].bad_suff) if(sum + t[v * 2 + 1].sum < a[pos - 1])
      |           ^
fish2.cpp: In function 'void seg::upd(int, int, int, int)':
fish2.cpp:137:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  137 |   for(auto[l, r]:t[v].bad_seg) {
      |           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 363556 KB Output is correct
2 Correct 265 ms 363560 KB Output is correct
3 Correct 248 ms 363604 KB Output is correct
4 Correct 274 ms 363560 KB Output is correct
5 Correct 268 ms 363620 KB Output is correct
6 Correct 278 ms 363688 KB Output is correct
7 Correct 267 ms 363580 KB Output is correct
8 Correct 261 ms 363580 KB Output is correct
9 Correct 281 ms 363468 KB Output is correct
10 Correct 254 ms 363576 KB Output is correct
11 Correct 268 ms 363540 KB Output is correct
12 Correct 268 ms 363540 KB Output is correct
13 Correct 262 ms 363604 KB Output is correct
14 Correct 258 ms 363672 KB Output is correct
15 Correct 268 ms 363524 KB Output is correct
16 Correct 263 ms 363568 KB Output is correct
17 Correct 281 ms 363508 KB Output is correct
18 Correct 259 ms 363576 KB Output is correct
19 Correct 255 ms 363572 KB Output is correct
20 Correct 261 ms 363604 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 363560 KB Output is correct
2 Correct 302 ms 368700 KB Output is correct
3 Correct 294 ms 367716 KB Output is correct
4 Correct 343 ms 368644 KB Output is correct
5 Correct 310 ms 367612 KB Output is correct
6 Correct 297 ms 367308 KB Output is correct
7 Correct 280 ms 367480 KB Output is correct
8 Correct 285 ms 367520 KB Output is correct
9 Correct 284 ms 367448 KB Output is correct
10 Correct 289 ms 367408 KB Output is correct
11 Correct 306 ms 367480 KB Output is correct
12 Correct 282 ms 367332 KB Output is correct
13 Correct 316 ms 367408 KB Output is correct
14 Correct 306 ms 367456 KB Output is correct
15 Correct 338 ms 367308 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 363556 KB Output is correct
2 Correct 265 ms 363560 KB Output is correct
3 Correct 248 ms 363604 KB Output is correct
4 Correct 274 ms 363560 KB Output is correct
5 Correct 268 ms 363620 KB Output is correct
6 Correct 278 ms 363688 KB Output is correct
7 Correct 267 ms 363580 KB Output is correct
8 Correct 261 ms 363580 KB Output is correct
9 Correct 281 ms 363468 KB Output is correct
10 Correct 254 ms 363576 KB Output is correct
11 Correct 268 ms 363540 KB Output is correct
12 Correct 268 ms 363540 KB Output is correct
13 Correct 262 ms 363604 KB Output is correct
14 Correct 258 ms 363672 KB Output is correct
15 Correct 268 ms 363524 KB Output is correct
16 Correct 263 ms 363568 KB Output is correct
17 Correct 281 ms 363508 KB Output is correct
18 Correct 259 ms 363576 KB Output is correct
19 Correct 255 ms 363572 KB Output is correct
20 Correct 261 ms 363604 KB Output is correct
21 Correct 258 ms 363560 KB Output is correct
22 Correct 302 ms 368700 KB Output is correct
23 Correct 294 ms 367716 KB Output is correct
24 Correct 343 ms 368644 KB Output is correct
25 Correct 310 ms 367612 KB Output is correct
26 Correct 297 ms 367308 KB Output is correct
27 Correct 280 ms 367480 KB Output is correct
28 Correct 285 ms 367520 KB Output is correct
29 Correct 284 ms 367448 KB Output is correct
30 Correct 289 ms 367408 KB Output is correct
31 Correct 306 ms 367480 KB Output is correct
32 Correct 282 ms 367332 KB Output is correct
33 Correct 316 ms 367408 KB Output is correct
34 Correct 306 ms 367456 KB Output is correct
35 Correct 338 ms 367308 KB Output is correct
36 Correct 341 ms 368964 KB Output is correct
37 Correct 349 ms 367820 KB Output is correct
38 Correct 369 ms 367828 KB Output is correct
39 Correct 329 ms 368860 KB Output is correct
40 Correct 345 ms 367924 KB Output is correct
41 Correct 314 ms 367416 KB Output is correct
42 Correct 310 ms 367416 KB Output is correct
43 Correct 336 ms 367516 KB Output is correct
44 Correct 306 ms 367416 KB Output is correct
45 Correct 326 ms 367532 KB Output is correct
46 Correct 315 ms 367320 KB Output is correct
47 Correct 334 ms 367436 KB Output is correct
48 Correct 394 ms 367416 KB Output is correct
49 Correct 328 ms 367412 KB Output is correct
50 Correct 302 ms 367512 KB Output is correct
51 Correct 336 ms 367348 KB Output is correct
52 Correct 309 ms 367540 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 363560 KB Output is correct
2 Correct 302 ms 368700 KB Output is correct
3 Correct 294 ms 367716 KB Output is correct
4 Correct 343 ms 368644 KB Output is correct
5 Correct 310 ms 367612 KB Output is correct
6 Correct 297 ms 367308 KB Output is correct
7 Correct 280 ms 367480 KB Output is correct
8 Correct 285 ms 367520 KB Output is correct
9 Correct 284 ms 367448 KB Output is correct
10 Correct 289 ms 367408 KB Output is correct
11 Correct 306 ms 367480 KB Output is correct
12 Correct 282 ms 367332 KB Output is correct
13 Correct 316 ms 367408 KB Output is correct
14 Correct 306 ms 367456 KB Output is correct
15 Correct 338 ms 367308 KB Output is correct
16 Correct 264 ms 363556 KB Output is correct
17 Execution timed out 4043 ms 368252 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 363560 KB Output is correct
2 Correct 302 ms 368700 KB Output is correct
3 Correct 294 ms 367716 KB Output is correct
4 Correct 343 ms 368644 KB Output is correct
5 Correct 310 ms 367612 KB Output is correct
6 Correct 297 ms 367308 KB Output is correct
7 Correct 280 ms 367480 KB Output is correct
8 Correct 285 ms 367520 KB Output is correct
9 Correct 284 ms 367448 KB Output is correct
10 Correct 289 ms 367408 KB Output is correct
11 Correct 306 ms 367480 KB Output is correct
12 Correct 282 ms 367332 KB Output is correct
13 Correct 316 ms 367408 KB Output is correct
14 Correct 306 ms 367456 KB Output is correct
15 Correct 338 ms 367308 KB Output is correct
16 Correct 254 ms 363560 KB Output is correct
17 Correct 1226 ms 368952 KB Output is correct
18 Correct 1038 ms 367864 KB Output is correct
19 Correct 1006 ms 367944 KB Output is correct
20 Correct 867 ms 368020 KB Output is correct
21 Correct 1192 ms 368872 KB Output is correct
22 Correct 1014 ms 368084 KB Output is correct
23 Correct 1205 ms 367928 KB Output is correct
24 Correct 962 ms 368000 KB Output is correct
25 Correct 1034 ms 367828 KB Output is correct
26 Correct 541 ms 367564 KB Output is correct
27 Correct 708 ms 367464 KB Output is correct
28 Correct 738 ms 367640 KB Output is correct
29 Correct 586 ms 367792 KB Output is correct
30 Correct 664 ms 367580 KB Output is correct
31 Correct 845 ms 367484 KB Output is correct
32 Correct 965 ms 367564 KB Output is correct
33 Correct 701 ms 367456 KB Output is correct
34 Correct 909 ms 367580 KB Output is correct
35 Correct 630 ms 367588 KB Output is correct
36 Correct 867 ms 367584 KB Output is correct
37 Correct 769 ms 367660 KB Output is correct
38 Correct 583 ms 367928 KB Output is correct
39 Correct 633 ms 367604 KB Output is correct
40 Correct 428 ms 367816 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 363556 KB Output is correct
2 Correct 265 ms 363560 KB Output is correct
3 Correct 248 ms 363604 KB Output is correct
4 Correct 274 ms 363560 KB Output is correct
5 Correct 268 ms 363620 KB Output is correct
6 Correct 278 ms 363688 KB Output is correct
7 Correct 267 ms 363580 KB Output is correct
8 Correct 261 ms 363580 KB Output is correct
9 Correct 281 ms 363468 KB Output is correct
10 Correct 254 ms 363576 KB Output is correct
11 Correct 268 ms 363540 KB Output is correct
12 Correct 268 ms 363540 KB Output is correct
13 Correct 262 ms 363604 KB Output is correct
14 Correct 258 ms 363672 KB Output is correct
15 Correct 268 ms 363524 KB Output is correct
16 Correct 263 ms 363568 KB Output is correct
17 Correct 281 ms 363508 KB Output is correct
18 Correct 259 ms 363576 KB Output is correct
19 Correct 255 ms 363572 KB Output is correct
20 Correct 261 ms 363604 KB Output is correct
21 Correct 258 ms 363560 KB Output is correct
22 Correct 302 ms 368700 KB Output is correct
23 Correct 294 ms 367716 KB Output is correct
24 Correct 343 ms 368644 KB Output is correct
25 Correct 310 ms 367612 KB Output is correct
26 Correct 297 ms 367308 KB Output is correct
27 Correct 280 ms 367480 KB Output is correct
28 Correct 285 ms 367520 KB Output is correct
29 Correct 284 ms 367448 KB Output is correct
30 Correct 289 ms 367408 KB Output is correct
31 Correct 306 ms 367480 KB Output is correct
32 Correct 282 ms 367332 KB Output is correct
33 Correct 316 ms 367408 KB Output is correct
34 Correct 306 ms 367456 KB Output is correct
35 Correct 338 ms 367308 KB Output is correct
36 Correct 341 ms 368964 KB Output is correct
37 Correct 349 ms 367820 KB Output is correct
38 Correct 369 ms 367828 KB Output is correct
39 Correct 329 ms 368860 KB Output is correct
40 Correct 345 ms 367924 KB Output is correct
41 Correct 314 ms 367416 KB Output is correct
42 Correct 310 ms 367416 KB Output is correct
43 Correct 336 ms 367516 KB Output is correct
44 Correct 306 ms 367416 KB Output is correct
45 Correct 326 ms 367532 KB Output is correct
46 Correct 315 ms 367320 KB Output is correct
47 Correct 334 ms 367436 KB Output is correct
48 Correct 394 ms 367416 KB Output is correct
49 Correct 328 ms 367412 KB Output is correct
50 Correct 302 ms 367512 KB Output is correct
51 Correct 336 ms 367348 KB Output is correct
52 Correct 309 ms 367540 KB Output is correct
53 Correct 264 ms 363556 KB Output is correct
54 Execution timed out 4043 ms 368252 KB Time limit exceeded
55 Halted 0 ms 0 KB -