oj.uz

Submission #617094

# Submission time Handle Problem Language Result Execution time Memory
617094 2022-08-01T08:40:28 Z cheissmart Fish 2 (JOI22_fish2) C++14
60 / 100
 4000 ms 253296 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 * 2];
	char tag[N * 2];
	int sum(int v, int h) {
		return tag[v] ? (1 << h) : t[v];
	}
	void pull(int p) {
		int h = 0;
	    while(p > 1) {
	        t[p >> 1] = sum(p, h) + sum(p ^ 1, h);
	        p >>= 1;
	        h++;
	    }
	}
	void add(int l, int r, int x) {
		if(l == 1 && r == n + 1) return;
		l--, r--;
		int tl = l, tr = r;
	    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
	    	if(l & 1) tag[l++] += x;
	    	if(r & 1) tag[--r] += x;
	    }
	    pull(tl + n), pull(tr - 1 + n);
	}
	int qry(int l, int r) {
		l--, r--; 
	    int res = 0, h = 0;
	    for(l += n, r += n; l < r; l >>= 1, r >>= 1, h++) {
	        if(l & 1) res += sum(l++, h);
	        if(r & 1) res += sum(--r, h);
	    }
	    return res;
	}
}

namespace seg {
	template<class A, class B> struct DS {
		pair<A, B> a[31];
		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 * 2];

	int id(int tl, int tr) {
		tl--, tr--;
		tr--;
	    return (tl + tr) | (tl != tr);
	}

	void pull(int v, int lc, int rc, int posl = INF, int posr = 0) {
		for(int i = 0; i < t[lc].bad_pref.sz; i++)
			t[v].bad_pref.PB(t[lc].bad_pref[i]);
		for(int i = 0; i < t[rc].bad_suff.sz; i++)
			t[v].bad_suff.PB(t[rc].bad_suff[i]);

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

		int szi = t[lc].bad_suff.sz;
		int szj = t[rc].bad_pref.sz;
		int i = 0, j = 0;
		while(i < szi && t[lc].bad_suff[i].F > posl)
			i++;
		while(j < szj && t[rc].bad_pref[j].F < posr)
			j++;
		while(i < szi && j < szj) {
			auto& he = t[lc].bad_suff[i], be = t[rc].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[lc].sum + t[rc].sum;
	}
	void build( int tl = 1, int tr = n + 1) {
		int v = id(tl, tr);
		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 + 1) / 2;
			build(tl, tm);
			build(tm, tr);
			pull(v, id(tl, tm), id(tm, tr));
		}
	}
	void upd(int pos, int tl = 1, int tr = n + 1) {
		int v = id(tl, tr);
		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 + 1) / 2;
			if(pos - 1 < tm)
				upd(pos, tl, tm);
			if(pos + 1 >= tm)
				upd(pos, tm, tr);
			pull(v, id(tl, tm), id(tm, tr), pos + 1, pos - 1);
		}
	}
}

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

#define gc getchar_unlocked
// #define gc getchar
inline int readInt () {
	int c = gc();
	while(!isdigit(c)) c = gc();
	int res = c - '0';
	while(true) {
		c = gc();
		if(isdigit(c)) res = res * 10 + c - '0';
		else break;
	}
	return res;
}

signed main()
{
	IO_OP;

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

	seg::build();

	int q;
	// cin >> q;
	q = readInt();
	while(q--) {
		int op;
		// cin >> op;
		op = readInt();
		if(op == 1) {
			int x, y;
			// cin >> x >> y;
			x = readInt(), y = readInt();
			upd(x, y);
		} else {
			int l, r;
			// cin >> l >> r;
			l = readInt(), r = readInt();
			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)':
fish2.cpp:153:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |    auto [l, r] = t[v].bad_seg[i];
      |         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 249164 KB Output is correct
2 Correct 112 ms 249224 KB Output is correct
3 Correct 109 ms 249192 KB Output is correct
4 Correct 121 ms 249352 KB Output is correct
5 Correct 145 ms 249232 KB Output is correct
6 Correct 130 ms 249312 KB Output is correct
7 Correct 113 ms 249320 KB Output is correct
8 Correct 146 ms 249164 KB Output is correct
9 Correct 119 ms 249228 KB Output is correct
10 Correct 107 ms 249236 KB Output is correct
11 Correct 107 ms 249180 KB Output is correct
12 Correct 132 ms 249184 KB Output is correct
13 Correct 121 ms 249268 KB Output is correct
14 Correct 110 ms 249172 KB Output is correct
15 Correct 111 ms 249172 KB Output is correct
16 Correct 113 ms 249276 KB Output is correct
17 Correct 116 ms 249252 KB Output is correct
18 Correct 137 ms 249284 KB Output is correct
19 Correct 115 ms 249168 KB Output is correct
20 Correct 117 ms 249164 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 249144 KB Output is correct
2 Correct 160 ms 251188 KB Output is correct
3 Correct 151 ms 250832 KB Output is correct
4 Correct 164 ms 251192 KB Output is correct
5 Correct 151 ms 250936 KB Output is correct
6 Correct 142 ms 251460 KB Output is correct
7 Correct 141 ms 250816 KB Output is correct
8 Correct 145 ms 251440 KB Output is correct
9 Correct 142 ms 250756 KB Output is correct
10 Correct 146 ms 251140 KB Output is correct
11 Correct 154 ms 250864 KB Output is correct
12 Correct 134 ms 250768 KB Output is correct
13 Correct 140 ms 250800 KB Output is correct
14 Correct 139 ms 251080 KB Output is correct
15 Correct 138 ms 251120 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 249164 KB Output is correct
2 Correct 112 ms 249224 KB Output is correct
3 Correct 109 ms 249192 KB Output is correct
4 Correct 121 ms 249352 KB Output is correct
5 Correct 145 ms 249232 KB Output is correct
6 Correct 130 ms 249312 KB Output is correct
7 Correct 113 ms 249320 KB Output is correct
8 Correct 146 ms 249164 KB Output is correct
9 Correct 119 ms 249228 KB Output is correct
10 Correct 107 ms 249236 KB Output is correct
11 Correct 107 ms 249180 KB Output is correct
12 Correct 132 ms 249184 KB Output is correct
13 Correct 121 ms 249268 KB Output is correct
14 Correct 110 ms 249172 KB Output is correct
15 Correct 111 ms 249172 KB Output is correct
16 Correct 113 ms 249276 KB Output is correct
17 Correct 116 ms 249252 KB Output is correct
18 Correct 137 ms 249284 KB Output is correct
19 Correct 115 ms 249168 KB Output is correct
20 Correct 117 ms 249164 KB Output is correct
21 Correct 129 ms 249144 KB Output is correct
22 Correct 160 ms 251188 KB Output is correct
23 Correct 151 ms 250832 KB Output is correct
24 Correct 164 ms 251192 KB Output is correct
25 Correct 151 ms 250936 KB Output is correct
26 Correct 142 ms 251460 KB Output is correct
27 Correct 141 ms 250816 KB Output is correct
28 Correct 145 ms 251440 KB Output is correct
29 Correct 142 ms 250756 KB Output is correct
30 Correct 146 ms 251140 KB Output is correct
31 Correct 154 ms 250864 KB Output is correct
32 Correct 134 ms 250768 KB Output is correct
33 Correct 140 ms 250800 KB Output is correct
34 Correct 139 ms 251080 KB Output is correct
35 Correct 138 ms 251120 KB Output is correct
36 Correct 165 ms 251116 KB Output is correct
37 Correct 174 ms 250964 KB Output is correct
38 Correct 196 ms 250944 KB Output is correct
39 Correct 168 ms 251308 KB Output is correct
40 Correct 182 ms 250988 KB Output is correct
41 Correct 146 ms 251516 KB Output is correct
42 Correct 154 ms 251556 KB Output is correct
43 Correct 162 ms 250832 KB Output is correct
44 Correct 178 ms 250792 KB Output is correct
45 Correct 159 ms 251136 KB Output is correct
46 Correct 160 ms 251084 KB Output is correct
47 Correct 175 ms 250840 KB Output is correct
48 Correct 140 ms 250816 KB Output is correct
49 Correct 152 ms 250844 KB Output is correct
50 Correct 175 ms 251152 KB Output is correct
51 Correct 157 ms 251340 KB Output is correct
52 Correct 154 ms 251228 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 249144 KB Output is correct
2 Correct 160 ms 251188 KB Output is correct
3 Correct 151 ms 250832 KB Output is correct
4 Correct 164 ms 251192 KB Output is correct
5 Correct 151 ms 250936 KB Output is correct
6 Correct 142 ms 251460 KB Output is correct
7 Correct 141 ms 250816 KB Output is correct
8 Correct 145 ms 251440 KB Output is correct
9 Correct 142 ms 250756 KB Output is correct
10 Correct 146 ms 251140 KB Output is correct
11 Correct 154 ms 250864 KB Output is correct
12 Correct 134 ms 250768 KB Output is correct
13 Correct 140 ms 250800 KB Output is correct
14 Correct 139 ms 251080 KB Output is correct
15 Correct 138 ms 251120 KB Output is correct
16 Correct 128 ms 249208 KB Output is correct
17 Execution timed out 4043 ms 252668 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 249144 KB Output is correct
2 Correct 160 ms 251188 KB Output is correct
3 Correct 151 ms 250832 KB Output is correct
4 Correct 164 ms 251192 KB Output is correct
5 Correct 151 ms 250936 KB Output is correct
6 Correct 142 ms 251460 KB Output is correct
7 Correct 141 ms 250816 KB Output is correct
8 Correct 145 ms 251440 KB Output is correct
9 Correct 142 ms 250756 KB Output is correct
10 Correct 146 ms 251140 KB Output is correct
11 Correct 154 ms 250864 KB Output is correct
12 Correct 134 ms 250768 KB Output is correct
13 Correct 140 ms 250800 KB Output is correct
14 Correct 139 ms 251080 KB Output is correct
15 Correct 138 ms 251120 KB Output is correct
16 Correct 117 ms 249192 KB Output is correct
17 Correct 711 ms 252468 KB Output is correct
18 Correct 590 ms 252620 KB Output is correct
19 Correct 632 ms 252056 KB Output is correct
20 Correct 521 ms 252644 KB Output is correct
21 Correct 643 ms 252152 KB Output is correct
22 Correct 623 ms 252572 KB Output is correct
23 Correct 632 ms 251996 KB Output is correct
24 Correct 579 ms 252652 KB Output is correct
25 Correct 705 ms 252120 KB Output is correct
26 Correct 334 ms 253188 KB Output is correct
27 Correct 412 ms 253252 KB Output is correct
28 Correct 412 ms 252544 KB Output is correct
29 Correct 334 ms 253164 KB Output is correct
30 Correct 423 ms 253296 KB Output is correct
31 Correct 510 ms 252544 KB Output is correct
32 Correct 552 ms 252568 KB Output is correct
33 Correct 368 ms 252168 KB Output is correct
34 Correct 548 ms 252884 KB Output is correct
35 Correct 334 ms 252528 KB Output is correct
36 Correct 553 ms 252504 KB Output is correct
37 Correct 480 ms 252376 KB Output is correct
38 Correct 401 ms 252260 KB Output is correct
39 Correct 371 ms 252904 KB Output is correct
40 Correct 246 ms 252820 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 249164 KB Output is correct
2 Correct 112 ms 249224 KB Output is correct
3 Correct 109 ms 249192 KB Output is correct
4 Correct 121 ms 249352 KB Output is correct
5 Correct 145 ms 249232 KB Output is correct
6 Correct 130 ms 249312 KB Output is correct
7 Correct 113 ms 249320 KB Output is correct
8 Correct 146 ms 249164 KB Output is correct
9 Correct 119 ms 249228 KB Output is correct
10 Correct 107 ms 249236 KB Output is correct
11 Correct 107 ms 249180 KB Output is correct
12 Correct 132 ms 249184 KB Output is correct
13 Correct 121 ms 249268 KB Output is correct
14 Correct 110 ms 249172 KB Output is correct
15 Correct 111 ms 249172 KB Output is correct
16 Correct 113 ms 249276 KB Output is correct
17 Correct 116 ms 249252 KB Output is correct
18 Correct 137 ms 249284 KB Output is correct
19 Correct 115 ms 249168 KB Output is correct
20 Correct 117 ms 249164 KB Output is correct
21 Correct 129 ms 249144 KB Output is correct
22 Correct 160 ms 251188 KB Output is correct
23 Correct 151 ms 250832 KB Output is correct
24 Correct 164 ms 251192 KB Output is correct
25 Correct 151 ms 250936 KB Output is correct
26 Correct 142 ms 251460 KB Output is correct
27 Correct 141 ms 250816 KB Output is correct
28 Correct 145 ms 251440 KB Output is correct
29 Correct 142 ms 250756 KB Output is correct
30 Correct 146 ms 251140 KB Output is correct
31 Correct 154 ms 250864 KB Output is correct
32 Correct 134 ms 250768 KB Output is correct
33 Correct 140 ms 250800 KB Output is correct
34 Correct 139 ms 251080 KB Output is correct
35 Correct 138 ms 251120 KB Output is correct
36 Correct 165 ms 251116 KB Output is correct
37 Correct 174 ms 250964 KB Output is correct
38 Correct 196 ms 250944 KB Output is correct
39 Correct 168 ms 251308 KB Output is correct
40 Correct 182 ms 250988 KB Output is correct
41 Correct 146 ms 251516 KB Output is correct
42 Correct 154 ms 251556 KB Output is correct
43 Correct 162 ms 250832 KB Output is correct
44 Correct 178 ms 250792 KB Output is correct
45 Correct 159 ms 251136 KB Output is correct
46 Correct 160 ms 251084 KB Output is correct
47 Correct 175 ms 250840 KB Output is correct
48 Correct 140 ms 250816 KB Output is correct
49 Correct 152 ms 250844 KB Output is correct
50 Correct 175 ms 251152 KB Output is correct
51 Correct 157 ms 251340 KB Output is correct
52 Correct 154 ms 251228 KB Output is correct
53 Correct 128 ms 249208 KB Output is correct
54 Execution timed out 4043 ms 252668 KB Time limit exceeded
55 Halted 0 ms 0 KB -