oj.uz

Submission #616538

# Submission time Handle Problem Language Result Execution time Memory
616538 2022-08-01T05:19:44 Z cheissmart Fish 2 (JOI22_fish2) C++14
60 / 100
 4000 ms 54648 KB 
// 花啊啊啊啊啊啊啊啊啊啊啊啊
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "no-stack-protector", "unroll-loops")
#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 {
	int t[N * 4];
	char tag[N * 4];
	int sum(int v, int len) {
		return tag[v] ? len : t[v];
	}
	void _add(int l, int r, int x, int v = 1, int tl = 1, int tr = n + 1) {
		if(l <= tl && tr <= r) {
			tag[v] += x;
			return;
		}
		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] = sum(v * 2, tm - tl) + sum(v * 2 + 1, tr - tm);
	}
	void add(int l, int r, int x) {
		if(l == 1 && r == n + 1) return;
		_add(l, r, x);
	}
	int qry(int l, int r, int v = 1, int tl = 1, int tr = n + 1) {
		if(l <= tl && tr <= r)
			return sum(v, tr - tl);
		int tm = (tl + tr) / 2, res = 0;
		if(l < tm) res += qry(l, r, v * 2, tl, tm);
		if(r > tm) 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;
		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];

	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);
			if(l != 1 || r != n)
				cover::add(l, r + 1, -1);

			cout << r - l + 1 - cover::qry(l, r + 1) << '\n';

			if(l != 1 || r != n)
				cover::add(l, r + 1, 1);

			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:66:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |   for(auto[pos, sum]:t[v * 2 + 1].bad_pref) if(sum + t[v * 2].sum < a[pos + 1])
      |           ^
fish2.cpp:68:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |   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:111:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |   for(auto[l, r]:t[v].bad_seg) {
      |           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31512 KB Output is correct
2 Correct 17 ms 31644 KB Output is correct
3 Correct 19 ms 31644 KB Output is correct
4 Correct 18 ms 31612 KB Output is correct
5 Correct 26 ms 31768 KB Output is correct
6 Correct 28 ms 31704 KB Output is correct
7 Correct 18 ms 31640 KB Output is correct
8 Correct 33 ms 31644 KB Output is correct
9 Correct 24 ms 31700 KB Output is correct
10 Correct 21 ms 31708 KB Output is correct
11 Correct 20 ms 31700 KB Output is correct
12 Correct 23 ms 31800 KB Output is correct
13 Correct 30 ms 31692 KB Output is correct
14 Correct 20 ms 31644 KB Output is correct
15 Correct 23 ms 31700 KB Output is correct
16 Correct 22 ms 31648 KB Output is correct
17 Correct 24 ms 31700 KB Output is correct
18 Correct 21 ms 31652 KB Output is correct
19 Correct 22 ms 31712 KB Output is correct
20 Correct 25 ms 31620 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 79 ms 48088 KB Output is correct
3 Correct 90 ms 46648 KB Output is correct
4 Correct 75 ms 47992 KB Output is correct
5 Correct 84 ms 46784 KB Output is correct
6 Correct 65 ms 42340 KB Output is correct
7 Correct 59 ms 40508 KB Output is correct
8 Correct 64 ms 41936 KB Output is correct
9 Correct 61 ms 40616 KB Output is correct
10 Correct 67 ms 47276 KB Output is correct
11 Correct 67 ms 43536 KB Output is correct
12 Correct 51 ms 41176 KB Output is correct
13 Correct 55 ms 41176 KB Output is correct
14 Correct 64 ms 44052 KB Output is correct
15 Correct 70 ms 43816 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31512 KB Output is correct
2 Correct 17 ms 31644 KB Output is correct
3 Correct 19 ms 31644 KB Output is correct
4 Correct 18 ms 31612 KB Output is correct
5 Correct 26 ms 31768 KB Output is correct
6 Correct 28 ms 31704 KB Output is correct
7 Correct 18 ms 31640 KB Output is correct
8 Correct 33 ms 31644 KB Output is correct
9 Correct 24 ms 31700 KB Output is correct
10 Correct 21 ms 31708 KB Output is correct
11 Correct 20 ms 31700 KB Output is correct
12 Correct 23 ms 31800 KB Output is correct
13 Correct 30 ms 31692 KB Output is correct
14 Correct 20 ms 31644 KB Output is correct
15 Correct 23 ms 31700 KB Output is correct
16 Correct 22 ms 31648 KB Output is correct
17 Correct 24 ms 31700 KB Output is correct
18 Correct 21 ms 31652 KB Output is correct
19 Correct 22 ms 31712 KB Output is correct
20 Correct 25 ms 31620 KB Output is correct
21 Correct 16 ms 31572 KB Output is correct
22 Correct 79 ms 48088 KB Output is correct
23 Correct 90 ms 46648 KB Output is correct
24 Correct 75 ms 47992 KB Output is correct
25 Correct 84 ms 46784 KB Output is correct
26 Correct 65 ms 42340 KB Output is correct
27 Correct 59 ms 40508 KB Output is correct
28 Correct 64 ms 41936 KB Output is correct
29 Correct 61 ms 40616 KB Output is correct
30 Correct 67 ms 47276 KB Output is correct
31 Correct 67 ms 43536 KB Output is correct
32 Correct 51 ms 41176 KB Output is correct
33 Correct 55 ms 41176 KB Output is correct
34 Correct 64 ms 44052 KB Output is correct
35 Correct 70 ms 43816 KB Output is correct
36 Correct 136 ms 48532 KB Output is correct
37 Correct 128 ms 46792 KB Output is correct
38 Correct 119 ms 46584 KB Output is correct
39 Correct 94 ms 48144 KB Output is correct
40 Correct 156 ms 46556 KB Output is correct
41 Correct 71 ms 42188 KB Output is correct
42 Correct 79 ms 42184 KB Output is correct
43 Correct 81 ms 41040 KB Output is correct
44 Correct 79 ms 40984 KB Output is correct
45 Correct 142 ms 47732 KB Output is correct
46 Correct 123 ms 47840 KB Output is correct
47 Correct 105 ms 42496 KB Output is correct
48 Correct 78 ms 41288 KB Output is correct
49 Correct 88 ms 41372 KB Output is correct
50 Correct 81 ms 44096 KB Output is correct
51 Correct 91 ms 43980 KB Output is correct
52 Correct 86 ms 44152 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 79 ms 48088 KB Output is correct
3 Correct 90 ms 46648 KB Output is correct
4 Correct 75 ms 47992 KB Output is correct
5 Correct 84 ms 46784 KB Output is correct
6 Correct 65 ms 42340 KB Output is correct
7 Correct 59 ms 40508 KB Output is correct
8 Correct 64 ms 41936 KB Output is correct
9 Correct 61 ms 40616 KB Output is correct
10 Correct 67 ms 47276 KB Output is correct
11 Correct 67 ms 43536 KB Output is correct
12 Correct 51 ms 41176 KB Output is correct
13 Correct 55 ms 41176 KB Output is correct
14 Correct 64 ms 44052 KB Output is correct
15 Correct 70 ms 43816 KB Output is correct
16 Correct 20 ms 31552 KB Output is correct
17 Execution timed out 4077 ms 52200 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 79 ms 48088 KB Output is correct
3 Correct 90 ms 46648 KB Output is correct
4 Correct 75 ms 47992 KB Output is correct
5 Correct 84 ms 46784 KB Output is correct
6 Correct 65 ms 42340 KB Output is correct
7 Correct 59 ms 40508 KB Output is correct
8 Correct 64 ms 41936 KB Output is correct
9 Correct 61 ms 40616 KB Output is correct
10 Correct 67 ms 47276 KB Output is correct
11 Correct 67 ms 43536 KB Output is correct
12 Correct 51 ms 41176 KB Output is correct
13 Correct 55 ms 41176 KB Output is correct
14 Correct 64 ms 44052 KB Output is correct
15 Correct 70 ms 43816 KB Output is correct
16 Correct 17 ms 31572 KB Output is correct
17 Correct 822 ms 48712 KB Output is correct
18 Correct 777 ms 54348 KB Output is correct
19 Correct 692 ms 46688 KB Output is correct
20 Correct 658 ms 53356 KB Output is correct
21 Correct 934 ms 48988 KB Output is correct
22 Correct 748 ms 54344 KB Output is correct
23 Correct 839 ms 46812 KB Output is correct
24 Correct 734 ms 54012 KB Output is correct
25 Correct 789 ms 46696 KB Output is correct
26 Correct 326 ms 45012 KB Output is correct
27 Correct 382 ms 46072 KB Output is correct
28 Correct 583 ms 48060 KB Output is correct
29 Correct 341 ms 45528 KB Output is correct
30 Correct 408 ms 46048 KB Output is correct
31 Correct 610 ms 48944 KB Output is correct
32 Correct 824 ms 52616 KB Output is correct
33 Correct 579 ms 43772 KB Output is correct
34 Correct 722 ms 54648 KB Output is correct
35 Correct 362 ms 47340 KB Output is correct
36 Correct 708 ms 51176 KB Output is correct
37 Correct 602 ms 46912 KB Output is correct
38 Correct 433 ms 45480 KB Output is correct
39 Correct 425 ms 47644 KB Output is correct
40 Correct 254 ms 45932 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31512 KB Output is correct
2 Correct 17 ms 31644 KB Output is correct
3 Correct 19 ms 31644 KB Output is correct
4 Correct 18 ms 31612 KB Output is correct
5 Correct 26 ms 31768 KB Output is correct
6 Correct 28 ms 31704 KB Output is correct
7 Correct 18 ms 31640 KB Output is correct
8 Correct 33 ms 31644 KB Output is correct
9 Correct 24 ms 31700 KB Output is correct
10 Correct 21 ms 31708 KB Output is correct
11 Correct 20 ms 31700 KB Output is correct
12 Correct 23 ms 31800 KB Output is correct
13 Correct 30 ms 31692 KB Output is correct
14 Correct 20 ms 31644 KB Output is correct
15 Correct 23 ms 31700 KB Output is correct
16 Correct 22 ms 31648 KB Output is correct
17 Correct 24 ms 31700 KB Output is correct
18 Correct 21 ms 31652 KB Output is correct
19 Correct 22 ms 31712 KB Output is correct
20 Correct 25 ms 31620 KB Output is correct
21 Correct 16 ms 31572 KB Output is correct
22 Correct 79 ms 48088 KB Output is correct
23 Correct 90 ms 46648 KB Output is correct
24 Correct 75 ms 47992 KB Output is correct
25 Correct 84 ms 46784 KB Output is correct
26 Correct 65 ms 42340 KB Output is correct
27 Correct 59 ms 40508 KB Output is correct
28 Correct 64 ms 41936 KB Output is correct
29 Correct 61 ms 40616 KB Output is correct
30 Correct 67 ms 47276 KB Output is correct
31 Correct 67 ms 43536 KB Output is correct
32 Correct 51 ms 41176 KB Output is correct
33 Correct 55 ms 41176 KB Output is correct
34 Correct 64 ms 44052 KB Output is correct
35 Correct 70 ms 43816 KB Output is correct
36 Correct 136 ms 48532 KB Output is correct
37 Correct 128 ms 46792 KB Output is correct
38 Correct 119 ms 46584 KB Output is correct
39 Correct 94 ms 48144 KB Output is correct
40 Correct 156 ms 46556 KB Output is correct
41 Correct 71 ms 42188 KB Output is correct
42 Correct 79 ms 42184 KB Output is correct
43 Correct 81 ms 41040 KB Output is correct
44 Correct 79 ms 40984 KB Output is correct
45 Correct 142 ms 47732 KB Output is correct
46 Correct 123 ms 47840 KB Output is correct
47 Correct 105 ms 42496 KB Output is correct
48 Correct 78 ms 41288 KB Output is correct
49 Correct 88 ms 41372 KB Output is correct
50 Correct 81 ms 44096 KB Output is correct
51 Correct 91 ms 43980 KB Output is correct
52 Correct 86 ms 44152 KB Output is correct
53 Correct 20 ms 31552 KB Output is correct
54 Execution timed out 4077 ms 52200 KB Time limit exceeded
55 Halted 0 ms 0 KB -