Submission #917230

#	Time	Username	Problem	Language	Result	Execution time	Memory
917230		thangdz2k7	Fish 2 (JOI22_fish2)	C++17	100 / 100	1712 ms	38484 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15 + 5;
const int N = 1e5 + 5;
int n, q;
long long a[N];
set<int> rp[N], lp[N];
namespace ST {
	pair<int, int> t[N << 2];
	int lazy[N << 2];
	inline pair<int, int> operator+(const pair<int, int> &lhs, const pair<int, int> &rhs) {
		if (lhs.first != rhs.first) return min(lhs, rhs);
		return {lhs.first, lhs.second + rhs.second}; 
	}
	inline void push_up(int p) {
		t[p] = t[p << 1] + t[p << 1 | 1];
	}
	inline void tag(int p, int x) {
		t[p].first += x;
		lazy[p] += x;
	}
	inline void push_down(int p) {
		if (lazy[p]) {
			tag(p << 1, lazy[p]);
			tag(p << 1 | 1, lazy[p]);
			lazy[p] = 0;
		}
	}
	void build(int p, int l, int r) {
		t[p].second = r - l + 1;
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
	}
	void modify(int p, int l, int r, int ll, int rr, int x) {
		if (l >= ll && r <= rr) {
			tag(p, x);
			return;
		}
		push_down(p);
		int mid = (l + r) >> 1;
		if (mid >= ll) modify(p << 1, l, mid, ll, rr, x);
		if (mid < rr) modify(p << 1 | 1, mid + 1, r, ll, rr, x);
		push_up(p);
	}
	pair<int, int> query(int p, int l, int r, int ll, int rr) {
		if (l >= ll && r <= rr) return t[p];
		push_down(p);
		int mid = (l + r) >> 1;
		if (mid >= ll && mid < rr) return query(p << 1, l, mid, ll, rr) + query(p << 1 | 1, mid + 1, r, ll, rr);
		if (mid >= ll) return query(p << 1, l, mid, ll, rr);
		return query(p << 1 | 1, mid + 1, r, ll, rr); 
	}
}
namespace BIT {
	long long c[N];
	inline void modify(int p, long long x) {
		for (; p <= n; p += p & -p)
			c[p] += x;
	}
	inline long long query(int p) {
		long long res = 0;
		for (; p; p -= p & -p)
			res += c[p];
		return res;
	}
	inline long long query(int l, int r) {
		return query(r) - query(l - 1);
	}
}
namespace ST1 {
	long long val[N << 2], lazy[N << 2];
	inline void push_up(int p) {
		val[p] = min(val[p << 1], val[p << 1 | 1]);
	}
	inline void tag(int p, long long x) {
		val[p] += x;
		lazy[p] += x;
	}
	inline void push_down(int p) {
		if (lazy[p]) {
			tag(p << 1, lazy[p]);
			tag(p << 1 | 1, lazy[p]);
			lazy[p] = 0;
		}
	}
	void modify(int p, int l, int r, int ll, int rr, long long x) {
		if (l >= ll && r <= rr) {
			tag(p, x);
			return;
		}
		push_down(p);
		int mid = (l + r) >> 1;
		if (mid >= ll) modify(p << 1, l, mid, ll, rr, x);
		if (mid < rr) modify(p << 1 | 1, mid + 1, r, ll, rr, x);
		push_up(p);
	}
	long long find_l(int p, int l, int r, int pos, long long x) {
		if (val[p] >= x) return -1;
		if (l == r) return l;
		push_down(p);
		int mid = (l + r) >> 1;
		if (pos <= mid) return find_l(p << 1, l, mid, pos, x);
		int res = find_l(p << 1 | 1, mid + 1, r, pos, x);
		return ~res ? res : find_l(p << 1, l, mid, pos, x); 
	}
	long long find_r(int p, int l, int r, int pos, long long x) {
		if (val[p] >= x) return -1;
		if (l == r) return l;
		push_down(p);
		int mid = (l + r) >> 1;
		if (pos > mid) return find_r(p << 1 | 1, mid + 1, r, pos, x);
		int res = find_r(p << 1, l, mid, pos, x);
		return ~res ? res : find_r(p << 1 | 1, mid + 1, r, pos, x);
	}
}
namespace ST2 {
	long long val[N << 2], lazy[N << 2];
	inline void push_up(int p) {
		val[p] = max(val[p << 1], val[p << 1 | 1]);
	}
	inline void tag(int p, long long x) {
		val[p] += x;
		lazy[p] += x;
	}
	inline void push_down(int p) {
		if (lazy[p]) {
			tag(p << 1, lazy[p]);
			tag(p << 1 | 1, lazy[p]);
			lazy[p] = 0;
		}
	}
	void modify(int p, int l, int r, int ll, int rr, long long x) {
		if (l >= ll && r <= rr) {
			tag(p, x);
			return;
		}
		push_down(p);
		int mid = (l + r) >> 1;
		if (mid >= ll) modify(p << 1, l, mid, ll, rr, x);
		if (mid < rr) modify(p << 1 | 1, mid + 1, r, ll, rr, x);
		push_up(p);
	}
	long long find_l(int p, int l, int r, int pos, long long x) {
		if (val[p] <= x) return -1;
		if (l == r) return l;
		push_down(p);
		int mid = (l + r) >> 1;
		if (pos <= mid) return find_l(p << 1, l, mid, pos, x);
		int res = find_l(p << 1 | 1, mid + 1, r, pos, x);
		return ~res ? res : find_l(p << 1, l, mid, pos, x); 
	}
	long long find_r(int p, int l, int r, int pos, long long x) {
		if (val[p] <= x) return -1;
		if (l == r) return l;
		push_down(p);
		int mid = (l + r) >> 1;
		if (pos > mid) return find_r(p << 1 | 1, mid + 1, r, pos, x);
		int res = find_r(p << 1, l, mid, pos, x);
		return ~res ? res : find_r(p << 1 | 1, mid + 1, r, pos, x);
	}
}
inline bool judge(int l, int r) {
	if (r - l <= 1) return false;
	return BIT::query(l + 1, r - 1) < min(a[l], a[r]);
}
void modify_seg(int l, int r, int x) {
	ST::modify(1, 1, n, l + 1, r - 1, x);
	if (x == 1) {
		lp[l].insert(r);
		rp[r].insert(l);
	} else {
		lp[l].erase(r);
		rp[r].erase(l);
	} 
}
int find_r(int l, int r) {
	return ST1::find_r(1, 0, n + 1, r + 1, BIT::query(l));
}
int find_l(int l, int r) {
	return ST2::find_l(1, 0, n + 1, l - 1, BIT::query(r - 1));
}
void check(int pos, int x) {
	int l = pos - 1, r = pos + 1;
	while (true) {
		if (judge(l, r)) modify_seg(l, r, x);
		if (l == 0 && r == n + 1) break;
		if (a[l] < a[r]) l = find_l(l, r);	
		else r = find_r(l, r);
	}
}
void modify(int pos, long long x) {
	check(pos, -1);
	BIT::modify(pos, x - a[pos]);
	ST1::modify(1, 0, n + 1, pos + 1, n + 1, x - a[pos]);
	ST1::modify(1, 0, n + 1, pos, pos, -(x - a[pos]));
	ST2::modify(1, 0, n + 1, pos, n + 1, x - a[pos]);
	ST2::modify(1, 0, n + 1, pos, pos, x - a[pos]);
	a[pos] = x;
	while (!rp[pos].empty()) {
		int l = *rp[pos].begin();
		modify_seg(l, pos, -1);
	}
	while (!lp[pos].empty()) {
		int r = *lp[pos].begin();
		modify_seg(pos, r, -1);
	}
	lp[pos].clear(), rp[pos].clear();
	int r = find_r(pos, pos + 1);
	while (true) {
		if (judge(pos, r)) modify_seg(pos, r, 1);
		if (r == n + 1) break;
		r = find_r(pos, r);
	} 
	int l = find_l(pos - 1, pos);
	while (true) {
		if (judge(l, pos)) modify_seg(l, pos, 1);
		if (l == 0) break;
		l = find_l(l, pos); 
	}
	check(pos, 1);
}
int main() {
	scanf("%d", &n);
	ST::build(1, 1, n);
	a[0] = a[n + 1] = inf;
	ST1::modify(1, 0, n + 1, n + 1, n + 1, -inf);
	ST2::modify(1, 0, n + 1, 0, 0, inf);
	modify_seg(0, n + 1, 1);
	long long tmp;
	for (int i = 1; i <= n; ++i)
		scanf("%lld", &tmp), modify(i, tmp);
	scanf("%d", &q);
	while (q--) {
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {
			modify(x, y);
		} else {
			int l = ST1::find_l(1, 0, n + 1, y, BIT::query(x - 1));
			int r = ST2::find_r(1, 0, n + 1, x, BIT::query(y));
			printf("%d\n", ST::query(1, 1, n, l, r).second);
		}
	}
	return 0;
}

Compilation message (stderr)

fish2.cpp: In function 'int main()':
fish2.cpp:225:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
fish2.cpp:233:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |   scanf("%lld", &tmp), modify(i, tmp);
      |   ~~~~~^~~~~~~~~~~~~~
fish2.cpp:234:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
fish2.cpp:237:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  237 |   scanf("%d%d%d", &op, &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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