제출 #616746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
616746		cheissmart	Fish 2 (JOI22_fish2)	C++14	60 / 100	4105 ms	652980 KiB

fish2

// 花啊啊啊啊啊啊啊啊啊啊啊啊
#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 DS {
		pair<int, ll> a[50];
		int sz;
		DS() { sz = 0; }
		void clear() { sz = 0; }
		void EB(int x, ll y) { a[sz++] = {x, y}; }
		void PB(pair<int, ll> p) { a[sz++] = p; }
		int size() { return sz; }
		pair<int, ll>& operator[](int i) { return a[i]; }
	};

	struct node {
		DS bad_pref, bad_suff;

		V<pi> 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);
		}
	}

}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 17