oj.uz

Submission #616763

# Submission time Handle Problem Language Result Execution time Memory
616763 2022-08-01T06:40:03 Z cheissmart Fish 2 (JOI22_fish2) C++14
48 / 100
 4000 ms 981940 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 {
	template<class A, class B> struct DS {
		pair<A, B> a[30];
		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; }
		int size() { return sz; }
		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[pos, sum] = t[v * 2 + 1].bad_pref[i];
			if(sum + t[v * 2].sum < a[pos + 1])
				t[v].bad_pref.EB(pos, sum + t[v * 2].sum);
		}
		for(int i = 0; i < t[v * 2].bad_suff.sz; i++) {
			auto[pos, sum] = t[v * 2].bad_suff[i];
			if(sum + t[v * 2 + 1].sum < a[pos - 1])
				t[v].bad_suff.EB(pos, sum + t[v * 2 + 1].sum);
		}

		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 < SZ(t[v].bad_seg); 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::pull(int, int, int)':
fish2.cpp:81:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |    auto[pos, sum] = t[v * 2 + 1].bad_pref[i];
      |        ^
fish2.cpp:86:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |    auto[pos, sum] = t[v * 2].bad_suff[i];
      |        ^
fish2.cpp: In function 'void seg::upd(int, int, int, int)':
fish2.cpp:132:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |    auto [l, r] = t[v].bad_seg[i];
      |         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 482520 KB Output is correct
2 Correct 241 ms 482460 KB Output is correct
3 Correct 230 ms 482492 KB Output is correct
4 Correct 270 ms 482516 KB Output is correct
5 Correct 258 ms 482508 KB Output is correct
6 Correct 220 ms 482488 KB Output is correct
7 Correct 248 ms 482488 KB Output is correct
8 Correct 257 ms 482568 KB Output is correct
9 Correct 253 ms 482548 KB Output is correct
10 Correct 269 ms 482548 KB Output is correct
11 Correct 228 ms 482568 KB Output is correct
12 Correct 248 ms 482452 KB Output is correct
13 Correct 229 ms 482560 KB Output is correct
14 Correct 223 ms 482568 KB Output is correct
15 Correct 231 ms 482524 KB Output is correct
16 Correct 234 ms 482556 KB Output is correct
17 Correct 219 ms 482468 KB Output is correct
18 Correct 242 ms 482508 KB Output is correct
19 Correct 255 ms 482468 KB Output is correct
20 Correct 243 ms 482508 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 482496 KB Output is correct
2 Correct 273 ms 484612 KB Output is correct
3 Correct 274 ms 484364 KB Output is correct
4 Correct 271 ms 484572 KB Output is correct
5 Correct 269 ms 484424 KB Output is correct
6 Correct 284 ms 484928 KB Output is correct
7 Correct 254 ms 484224 KB Output is correct
8 Correct 283 ms 485020 KB Output is correct
9 Correct 243 ms 484248 KB Output is correct
10 Correct 270 ms 484668 KB Output is correct
11 Correct 272 ms 484340 KB Output is correct
12 Correct 272 ms 484416 KB Output is correct
13 Correct 302 ms 484284 KB Output is correct
14 Correct 287 ms 484664 KB Output is correct
15 Correct 273 ms 484600 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 482520 KB Output is correct
2 Correct 241 ms 482460 KB Output is correct
3 Correct 230 ms 482492 KB Output is correct
4 Correct 270 ms 482516 KB Output is correct
5 Correct 258 ms 482508 KB Output is correct
6 Correct 220 ms 482488 KB Output is correct
7 Correct 248 ms 482488 KB Output is correct
8 Correct 257 ms 482568 KB Output is correct
9 Correct 253 ms 482548 KB Output is correct
10 Correct 269 ms 482548 KB Output is correct
11 Correct 228 ms 482568 KB Output is correct
12 Correct 248 ms 482452 KB Output is correct
13 Correct 229 ms 482560 KB Output is correct
14 Correct 223 ms 482568 KB Output is correct
15 Correct 231 ms 482524 KB Output is correct
16 Correct 234 ms 482556 KB Output is correct
17 Correct 219 ms 482468 KB Output is correct
18 Correct 242 ms 482508 KB Output is correct
19 Correct 255 ms 482468 KB Output is correct
20 Correct 243 ms 482508 KB Output is correct
21 Correct 238 ms 482496 KB Output is correct
22 Correct 273 ms 484612 KB Output is correct
23 Correct 274 ms 484364 KB Output is correct
24 Correct 271 ms 484572 KB Output is correct
25 Correct 269 ms 484424 KB Output is correct
26 Correct 284 ms 484928 KB Output is correct
27 Correct 254 ms 484224 KB Output is correct
28 Correct 283 ms 485020 KB Output is correct
29 Correct 243 ms 484248 KB Output is correct
30 Correct 270 ms 484668 KB Output is correct
31 Correct 272 ms 484340 KB Output is correct
32 Correct 272 ms 484416 KB Output is correct
33 Correct 302 ms 484284 KB Output is correct
34 Correct 287 ms 484664 KB Output is correct
35 Correct 273 ms 484600 KB Output is correct
36 Runtime error 770 ms 981940 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 482496 KB Output is correct
2 Correct 273 ms 484612 KB Output is correct
3 Correct 274 ms 484364 KB Output is correct
4 Correct 271 ms 484572 KB Output is correct
5 Correct 269 ms 484424 KB Output is correct
6 Correct 284 ms 484928 KB Output is correct
7 Correct 254 ms 484224 KB Output is correct
8 Correct 283 ms 485020 KB Output is correct
9 Correct 243 ms 484248 KB Output is correct
10 Correct 270 ms 484668 KB Output is correct
11 Correct 272 ms 484340 KB Output is correct
12 Correct 272 ms 484416 KB Output is correct
13 Correct 302 ms 484284 KB Output is correct
14 Correct 287 ms 484664 KB Output is correct
15 Correct 273 ms 484600 KB Output is correct
16 Correct 255 ms 482484 KB Output is correct
17 Execution timed out 4096 ms 485716 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 482496 KB Output is correct
2 Correct 273 ms 484612 KB Output is correct
3 Correct 274 ms 484364 KB Output is correct
4 Correct 271 ms 484572 KB Output is correct
5 Correct 269 ms 484424 KB Output is correct
6 Correct 284 ms 484928 KB Output is correct
7 Correct 254 ms 484224 KB Output is correct
8 Correct 283 ms 485020 KB Output is correct
9 Correct 243 ms 484248 KB Output is correct
10 Correct 270 ms 484668 KB Output is correct
11 Correct 272 ms 484340 KB Output is correct
12 Correct 272 ms 484416 KB Output is correct
13 Correct 302 ms 484284 KB Output is correct
14 Correct 287 ms 484664 KB Output is correct
15 Correct 273 ms 484600 KB Output is correct
16 Correct 266 ms 482464 KB Output is correct
17 Correct 1246 ms 485632 KB Output is correct
18 Correct 928 ms 486036 KB Output is correct
19 Correct 1025 ms 485564 KB Output is correct
20 Correct 728 ms 486192 KB Output is correct
21 Correct 1152 ms 485636 KB Output is correct
22 Correct 834 ms 486096 KB Output is correct
23 Correct 997 ms 485424 KB Output is correct
24 Correct 876 ms 486004 KB Output is correct
25 Correct 798 ms 485604 KB Output is correct
26 Correct 524 ms 486268 KB Output is correct
27 Correct 576 ms 486108 KB Output is correct
28 Correct 693 ms 485912 KB Output is correct
29 Correct 554 ms 486048 KB Output is correct
30 Correct 548 ms 485784 KB Output is correct
31 Correct 704 ms 485884 KB Output is correct
32 Correct 843 ms 485748 KB Output is correct
33 Correct 653 ms 485632 KB Output is correct
34 Correct 1006 ms 485592 KB Output is correct
35 Correct 554 ms 485488 KB Output is correct
36 Correct 804 ms 485480 KB Output is correct
37 Correct 668 ms 485472 KB Output is correct
38 Correct 523 ms 485512 KB Output is correct
39 Correct 606 ms 485308 KB Output is correct
40 Correct 464 ms 485504 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 482520 KB Output is correct
2 Correct 241 ms 482460 KB Output is correct
3 Correct 230 ms 482492 KB Output is correct
4 Correct 270 ms 482516 KB Output is correct
5 Correct 258 ms 482508 KB Output is correct
6 Correct 220 ms 482488 KB Output is correct
7 Correct 248 ms 482488 KB Output is correct
8 Correct 257 ms 482568 KB Output is correct
9 Correct 253 ms 482548 KB Output is correct
10 Correct 269 ms 482548 KB Output is correct
11 Correct 228 ms 482568 KB Output is correct
12 Correct 248 ms 482452 KB Output is correct
13 Correct 229 ms 482560 KB Output is correct
14 Correct 223 ms 482568 KB Output is correct
15 Correct 231 ms 482524 KB Output is correct
16 Correct 234 ms 482556 KB Output is correct
17 Correct 219 ms 482468 KB Output is correct
18 Correct 242 ms 482508 KB Output is correct
19 Correct 255 ms 482468 KB Output is correct
20 Correct 243 ms 482508 KB Output is correct
21 Correct 238 ms 482496 KB Output is correct
22 Correct 273 ms 484612 KB Output is correct
23 Correct 274 ms 484364 KB Output is correct
24 Correct 271 ms 484572 KB Output is correct
25 Correct 269 ms 484424 KB Output is correct
26 Correct 284 ms 484928 KB Output is correct
27 Correct 254 ms 484224 KB Output is correct
28 Correct 283 ms 485020 KB Output is correct
29 Correct 243 ms 484248 KB Output is correct
30 Correct 270 ms 484668 KB Output is correct
31 Correct 272 ms 484340 KB Output is correct
32 Correct 272 ms 484416 KB Output is correct
33 Correct 302 ms 484284 KB Output is correct
34 Correct 287 ms 484664 KB Output is correct
35 Correct 273 ms 484600 KB Output is correct
36 Runtime error 770 ms 981940 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -