oj.uz

Submission #616828

# Submission time Handle Problem Language Result Execution time Memory
616828 2022-08-01T07:04:38 Z cheissmart Fish 2 (JOI22_fish2) C++14
60 / 100
 4000 ms 517744 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 {
	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 {
	template<class A, class B> struct DS {
		pair<A, B> a[32];
		int sz;
		DS() { sz = 0; }
		void clear() { sz = 0; }
		void EB(A x, B y) { a[sz++] = {x, y}; }
		void PB(pair<A, B> p) { a[sz++] = p; }
		pair<A, B>& operator[](int i) { return a[i]; }
		void resize(int s) { sz = s; }
	};

	struct node {
		DS<int, ll> bad_pref, bad_suff;
		DS<int, int> bad_seg;
		ll sum;
	} t[N * 4];
	void pull(int v, int posl = INF, int posr = 0) {
		for(int i = 0; i < t[v * 2].bad_pref.sz; i++)
			t[v].bad_pref.PB(t[v * 2].bad_pref[i]);
		for(int i = 0; i < t[v * 2 + 1].bad_suff.sz; i++)
			t[v].bad_suff.PB(t[v * 2 + 1].bad_suff[i]);

		for(int i = 0; i < t[v * 2 + 1].bad_pref.sz; i++) {
			// auto[pos1, sum1] = t[v * 2 + 1].bad_pref[i];
			#define pos1 t[v * 2 + 1].bad_pref[i].F
			#define sum1 t[v * 2 + 1].bad_pref[i].S
			if(sum1 + t[v * 2].sum < a[pos1 + 1])
				t[v].bad_pref.EB(pos1, sum1 + t[v * 2].sum);
			#undef pos1
			#undef sum1
		}
		for(int i = 0; i < t[v * 2].bad_suff.sz; i++) {
			// auto[pos1, sum1] = t[v * 2].bad_suff[i];
			#define pos1 t[v * 2].bad_suff[i].F
			#define sum1 t[v * 2].bad_suff[i].S
			if(sum1 + t[v * 2 + 1].sum < a[pos1 - 1])
				t[v].bad_suff.EB(pos1, sum1 + t[v * 2 + 1].sum);
			#undef pos1
			#undef sum1
		}

		int szi = t[v * 2].bad_suff.sz;
		int szj = t[v * 2 + 1].bad_pref.sz;
		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) {
		int j = 0;
		for(int i = 0; i < t[v].bad_seg.sz; i++) {
			auto [l, r] = t[v].bad_seg[i];
			if(r < pos - 1 || l > pos + 1) {
				t[v].bad_seg[j++] = t[v].bad_seg[i];
			} else {
				cover::add(l, r + 1, -1);
			}
		}
		t[v].bad_seg.resize(j);

		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::upd(int, int, int, int)':
fish2.cpp:139:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  139 |    auto [l, r] = t[v].bad_seg[i];
      |         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 513832 KB Output is correct
2 Correct 245 ms 513744 KB Output is correct
3 Correct 269 ms 513812 KB Output is correct
4 Correct 253 ms 513864 KB Output is correct
5 Correct 252 ms 513860 KB Output is correct
6 Correct 255 ms 513820 KB Output is correct
7 Correct 237 ms 513772 KB Output is correct
8 Correct 242 ms 513824 KB Output is correct
9 Correct 236 ms 513764 KB Output is correct
10 Correct 233 ms 513868 KB Output is correct
11 Correct 262 ms 513860 KB Output is correct
12 Correct 246 ms 513812 KB Output is correct
13 Correct 246 ms 513864 KB Output is correct
14 Correct 258 ms 513760 KB Output is correct
15 Correct 274 ms 513844 KB Output is correct
16 Correct 255 ms 513764 KB Output is correct
17 Correct 244 ms 513800 KB Output is correct
18 Correct 243 ms 513840 KB Output is correct
19 Correct 248 ms 513808 KB Output is correct
20 Correct 241 ms 513852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 513844 KB Output is correct
2 Correct 280 ms 515884 KB Output is correct
3 Correct 287 ms 515636 KB Output is correct
4 Correct 291 ms 515980 KB Output is correct
5 Correct 298 ms 515720 KB Output is correct
6 Correct 279 ms 516360 KB Output is correct
7 Correct 267 ms 515612 KB Output is correct
8 Correct 284 ms 516360 KB Output is correct
9 Correct 277 ms 515584 KB Output is correct
10 Correct 293 ms 516048 KB Output is correct
11 Correct 268 ms 515660 KB Output is correct
12 Correct 267 ms 515628 KB Output is correct
13 Correct 293 ms 515540 KB Output is correct
14 Correct 306 ms 515948 KB Output is correct
15 Correct 279 ms 515996 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 513832 KB Output is correct
2 Correct 245 ms 513744 KB Output is correct
3 Correct 269 ms 513812 KB Output is correct
4 Correct 253 ms 513864 KB Output is correct
5 Correct 252 ms 513860 KB Output is correct
6 Correct 255 ms 513820 KB Output is correct
7 Correct 237 ms 513772 KB Output is correct
8 Correct 242 ms 513824 KB Output is correct
9 Correct 236 ms 513764 KB Output is correct
10 Correct 233 ms 513868 KB Output is correct
11 Correct 262 ms 513860 KB Output is correct
12 Correct 246 ms 513812 KB Output is correct
13 Correct 246 ms 513864 KB Output is correct
14 Correct 258 ms 513760 KB Output is correct
15 Correct 274 ms 513844 KB Output is correct
16 Correct 255 ms 513764 KB Output is correct
17 Correct 244 ms 513800 KB Output is correct
18 Correct 243 ms 513840 KB Output is correct
19 Correct 248 ms 513808 KB Output is correct
20 Correct 241 ms 513852 KB Output is correct
21 Correct 238 ms 513844 KB Output is correct
22 Correct 280 ms 515884 KB Output is correct
23 Correct 287 ms 515636 KB Output is correct
24 Correct 291 ms 515980 KB Output is correct
25 Correct 298 ms 515720 KB Output is correct
26 Correct 279 ms 516360 KB Output is correct
27 Correct 267 ms 515612 KB Output is correct
28 Correct 284 ms 516360 KB Output is correct
29 Correct 277 ms 515584 KB Output is correct
30 Correct 293 ms 516048 KB Output is correct
31 Correct 268 ms 515660 KB Output is correct
32 Correct 267 ms 515628 KB Output is correct
33 Correct 293 ms 515540 KB Output is correct
34 Correct 306 ms 515948 KB Output is correct
35 Correct 279 ms 515996 KB Output is correct
36 Correct 308 ms 516200 KB Output is correct
37 Correct 312 ms 515660 KB Output is correct
38 Correct 314 ms 515768 KB Output is correct
39 Correct 303 ms 515916 KB Output is correct
40 Correct 334 ms 515804 KB Output is correct
41 Correct 308 ms 516296 KB Output is correct
42 Correct 313 ms 516344 KB Output is correct
43 Correct 297 ms 515584 KB Output is correct
44 Correct 285 ms 515548 KB Output is correct
45 Correct 295 ms 515916 KB Output is correct
46 Correct 298 ms 515936 KB Output is correct
47 Correct 293 ms 515808 KB Output is correct
48 Correct 278 ms 515700 KB Output is correct
49 Correct 322 ms 515720 KB Output is correct
50 Correct 303 ms 515912 KB Output is correct
51 Correct 299 ms 515912 KB Output is correct
52 Correct 310 ms 516000 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 513844 KB Output is correct
2 Correct 280 ms 515884 KB Output is correct
3 Correct 287 ms 515636 KB Output is correct
4 Correct 291 ms 515980 KB Output is correct
5 Correct 298 ms 515720 KB Output is correct
6 Correct 279 ms 516360 KB Output is correct
7 Correct 267 ms 515612 KB Output is correct
8 Correct 284 ms 516360 KB Output is correct
9 Correct 277 ms 515584 KB Output is correct
10 Correct 293 ms 516048 KB Output is correct
11 Correct 268 ms 515660 KB Output is correct
12 Correct 267 ms 515628 KB Output is correct
13 Correct 293 ms 515540 KB Output is correct
14 Correct 306 ms 515948 KB Output is correct
15 Correct 279 ms 515996 KB Output is correct
16 Correct 257 ms 513836 KB Output is correct
17 Execution timed out 4070 ms 517028 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 513844 KB Output is correct
2 Correct 280 ms 515884 KB Output is correct
3 Correct 287 ms 515636 KB Output is correct
4 Correct 291 ms 515980 KB Output is correct
5 Correct 298 ms 515720 KB Output is correct
6 Correct 279 ms 516360 KB Output is correct
7 Correct 267 ms 515612 KB Output is correct
8 Correct 284 ms 516360 KB Output is correct
9 Correct 277 ms 515584 KB Output is correct
10 Correct 293 ms 516048 KB Output is correct
11 Correct 268 ms 515660 KB Output is correct
12 Correct 267 ms 515628 KB Output is correct
13 Correct 293 ms 515540 KB Output is correct
14 Correct 306 ms 515948 KB Output is correct
15 Correct 279 ms 515996 KB Output is correct
16 Correct 279 ms 513792 KB Output is correct
17 Correct 1008 ms 516620 KB Output is correct
18 Correct 839 ms 516544 KB Output is correct
19 Correct 776 ms 516728 KB Output is correct
20 Correct 677 ms 516800 KB Output is correct
21 Correct 1051 ms 516612 KB Output is correct
22 Correct 866 ms 516608 KB Output is correct
23 Correct 1097 ms 516844 KB Output is correct
24 Correct 876 ms 516836 KB Output is correct
25 Correct 1022 ms 516932 KB Output is correct
26 Correct 562 ms 517360 KB Output is correct
27 Correct 593 ms 517352 KB Output is correct
28 Correct 689 ms 517028 KB Output is correct
29 Correct 596 ms 517600 KB Output is correct
30 Correct 672 ms 517744 KB Output is correct
31 Correct 777 ms 517040 KB Output is correct
32 Correct 846 ms 517168 KB Output is correct
33 Correct 633 ms 516896 KB Output is correct
34 Correct 828 ms 517708 KB Output is correct
35 Correct 579 ms 517336 KB Output is correct
36 Correct 711 ms 517420 KB Output is correct
37 Correct 698 ms 517192 KB Output is correct
38 Correct 525 ms 517060 KB Output is correct
39 Correct 540 ms 517704 KB Output is correct
40 Correct 461 ms 517608 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 513832 KB Output is correct
2 Correct 245 ms 513744 KB Output is correct
3 Correct 269 ms 513812 KB Output is correct
4 Correct 253 ms 513864 KB Output is correct
5 Correct 252 ms 513860 KB Output is correct
6 Correct 255 ms 513820 KB Output is correct
7 Correct 237 ms 513772 KB Output is correct
8 Correct 242 ms 513824 KB Output is correct
9 Correct 236 ms 513764 KB Output is correct
10 Correct 233 ms 513868 KB Output is correct
11 Correct 262 ms 513860 KB Output is correct
12 Correct 246 ms 513812 KB Output is correct
13 Correct 246 ms 513864 KB Output is correct
14 Correct 258 ms 513760 KB Output is correct
15 Correct 274 ms 513844 KB Output is correct
16 Correct 255 ms 513764 KB Output is correct
17 Correct 244 ms 513800 KB Output is correct
18 Correct 243 ms 513840 KB Output is correct
19 Correct 248 ms 513808 KB Output is correct
20 Correct 241 ms 513852 KB Output is correct
21 Correct 238 ms 513844 KB Output is correct
22 Correct 280 ms 515884 KB Output is correct
23 Correct 287 ms 515636 KB Output is correct
24 Correct 291 ms 515980 KB Output is correct
25 Correct 298 ms 515720 KB Output is correct
26 Correct 279 ms 516360 KB Output is correct
27 Correct 267 ms 515612 KB Output is correct
28 Correct 284 ms 516360 KB Output is correct
29 Correct 277 ms 515584 KB Output is correct
30 Correct 293 ms 516048 KB Output is correct
31 Correct 268 ms 515660 KB Output is correct
32 Correct 267 ms 515628 KB Output is correct
33 Correct 293 ms 515540 KB Output is correct
34 Correct 306 ms 515948 KB Output is correct
35 Correct 279 ms 515996 KB Output is correct
36 Correct 308 ms 516200 KB Output is correct
37 Correct 312 ms 515660 KB Output is correct
38 Correct 314 ms 515768 KB Output is correct
39 Correct 303 ms 515916 KB Output is correct
40 Correct 334 ms 515804 KB Output is correct
41 Correct 308 ms 516296 KB Output is correct
42 Correct 313 ms 516344 KB Output is correct
43 Correct 297 ms 515584 KB Output is correct
44 Correct 285 ms 515548 KB Output is correct
45 Correct 295 ms 515916 KB Output is correct
46 Correct 298 ms 515936 KB Output is correct
47 Correct 293 ms 515808 KB Output is correct
48 Correct 278 ms 515700 KB Output is correct
49 Correct 322 ms 515720 KB Output is correct
50 Correct 303 ms 515912 KB Output is correct
51 Correct 299 ms 515912 KB Output is correct
52 Correct 310 ms 516000 KB Output is correct
53 Correct 257 ms 513836 KB Output is correct
54 Execution timed out 4070 ms 517028 KB Time limit exceeded
55 Halted 0 ms 0 KB -