Submission #616000

#	Time	Username	Problem	Language	Result	Execution time	Memory
616000		cheissmart	Fish 2 (JOI22_fish2)	C++14	60 / 100	4069 ms	56984 KiB

fish2

#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;
		ll sum;
	} t[N * 4];
	V<pi> pull(int v) {
		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);
		
		V<pi> bad_seg;
		for(int i = 0, j = 0; i < SZ(t[v * 2].bad_suff) && j < SZ(t[v * 2 + 1].bad_pref); ) {
			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]))
				bad_seg.EB(he.F, be.F);
			if(a[he.F - 1] < a[be.F + 1])
				i++;
			else
				j++;
		}
		t[v].sum = t[v * 2].sum + t[v * 2 + 1].sum;
		return bad_seg;
	}
	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);
		} else {
			int tm = (tl + tr) / 2;
			build(v * 2, tl, tm);
			build(v * 2 + 1, tm, tr);
			t[v].bad_seg = pull(v);
		}
		for(auto[l, r]:t[v].bad_seg)
			cover::add(l, r + 1, 1);
	}
	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);
			tt = pull(v);
			for(auto[l, r]:tt) {
				if(r < pos - 1 || l > pos + 1)
					continue;
				t[v].bad_seg.EB(l, r);
				cover::add(l, r + 1, 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 (stderr)

fish2.cpp: In function 'std::vector<std::pair<int, int> > seg::pull(int)':
fish2.cpp:86:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |   for(auto[pos, sum]:t[v * 2 + 1].bad_pref) if(sum + t[v * 2].sum < a[pos + 1])
      |           ^
fish2.cpp:88:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |   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::build(int, int, int)':
fish2.cpp:119:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |   for(auto[l, r]:t[v].bad_seg)
      |           ^
fish2.cpp: In function 'void seg::upd(int, int, int, int)':
fish2.cpp:124:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |   for(auto[l, r]:t[v].bad_seg) {
      |           ^
fish2.cpp:150:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  150 |    for(auto[l, r]:tt) {
      |            ^

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 17