oj.uz

Submission #615996

# Submission time Handle Problem Language Result Execution time Memory
615996 2022-07-31T17:37:22 Z cheissmart Fish 2 (JOI22_fish2) C++14
8 / 100
 111 ms 50696 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 {
	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) {
		for(auto p:t[v * 2].bad_pref)
			t[v].bad_pref.PB(p);
		for(auto p:t[v * 2 + 1].bad_suff)
			t[v].bad_suff.PB(p);
		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);
		} 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);
			}
		}
		for(auto[l, r]:t[v].bad_seg)
			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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 18 ms 31652 KB Output is correct
3 Incorrect 18 ms 31656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31552 KB Output is correct
2 Correct 99 ms 50696 KB Output is correct
3 Correct 97 ms 48972 KB Output is correct
4 Correct 111 ms 50660 KB Output is correct
5 Correct 87 ms 49076 KB Output is correct
6 Correct 68 ms 43900 KB Output is correct
7 Correct 57 ms 42696 KB Output is correct
8 Correct 62 ms 43912 KB Output is correct
9 Correct 56 ms 42700 KB Output is correct
10 Correct 76 ms 50408 KB Output is correct
11 Correct 75 ms 46084 KB Output is correct
12 Correct 59 ms 43384 KB Output is correct
13 Correct 73 ms 43468 KB Output is correct
14 Correct 84 ms 46076 KB Output is correct
15 Correct 73 ms 45984 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 18 ms 31652 KB Output is correct
3 Incorrect 18 ms 31656 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31552 KB Output is correct
2 Correct 99 ms 50696 KB Output is correct
3 Correct 97 ms 48972 KB Output is correct
4 Correct 111 ms 50660 KB Output is correct
5 Correct 87 ms 49076 KB Output is correct
6 Correct 68 ms 43900 KB Output is correct
7 Correct 57 ms 42696 KB Output is correct
8 Correct 62 ms 43912 KB Output is correct
9 Correct 56 ms 42700 KB Output is correct
10 Correct 76 ms 50408 KB Output is correct
11 Correct 75 ms 46084 KB Output is correct
12 Correct 59 ms 43384 KB Output is correct
13 Correct 73 ms 43468 KB Output is correct
14 Correct 84 ms 46076 KB Output is correct
15 Correct 73 ms 45984 KB Output is correct
16 Incorrect 15 ms 31572 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31552 KB Output is correct
2 Correct 99 ms 50696 KB Output is correct
3 Correct 97 ms 48972 KB Output is correct
4 Correct 111 ms 50660 KB Output is correct
5 Correct 87 ms 49076 KB Output is correct
6 Correct 68 ms 43900 KB Output is correct
7 Correct 57 ms 42696 KB Output is correct
8 Correct 62 ms 43912 KB Output is correct
9 Correct 56 ms 42700 KB Output is correct
10 Correct 76 ms 50408 KB Output is correct
11 Correct 75 ms 46084 KB Output is correct
12 Correct 59 ms 43384 KB Output is correct
13 Correct 73 ms 43468 KB Output is correct
14 Correct 84 ms 46076 KB Output is correct
15 Correct 73 ms 45984 KB Output is correct
16 Incorrect 16 ms 31572 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31572 KB Output is correct
2 Correct 18 ms 31652 KB Output is correct
3 Incorrect 18 ms 31656 KB Output isn't correct
4 Halted 0 ms 0 KB -