Submission #373267

#	Time	Username	Problem	Language	Result	Execution time	Memory
373267		rk42745417	Po (COCI21_po)	C++17	70 / 70	171 ms	3052 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define EMT ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 2e18;
const double EPS = 1e-9;

const int N = 1e5 + 25;
struct segtree {
	int arr[N << 2], tag[N << 2], n;

	inline void pull(int p) { arr[p] = min(arr[p << 1], arr[p << 1 | 1]) + tag[p]; }
	inline void push(int p) {
		arr[p << 1] += tag[p];
		tag[p << 1] += tag[p];
		arr[p << 1 | 1] += tag[p];
		tag[p << 1 | 1] += tag[p];
		tag[p] = 0;
	}
	inline void build(int l, int r, int id, vector<int> &w) {
		if(l == r - 1) {
			arr[id] = w[l];
			return;
		}
		int m = l + r >> 1;
		build(l, m, id << 1, w);
		build(m, r, id << 1 | 1, w);
		pull(id);
	}
	inline void init(vector<int> &w) { n = w.size(); build(0, n, 1, w); }
	int que(int l, int r, int id, int ql, int qr) {
		if(ql <= l && r <= qr)
			return arr[id];
		if(r <= ql || qr <= l)
			return INF;
		push(id);
		int m = l + r >> 1;
		return min(que(l, m, id << 1, ql, qr), que(m, r, id << 1 | 1, ql, qr));
	}
	inline int que(int l, int r) { return que(0, n, 1, l, r); }
	int get(int l, int r, int id, int ql) {
		if(r <= ql || arr[id])
			return INF;
		if(l == r - 1)
			return l;
		push(id);
		int m = l + r >> 1;
		int w = get(l, m, id << 1, ql);
		if(w == INF)
			return get(m, r, id << 1 | 1, ql);
		return w;
	}
	inline int get(int l) { return get(0, n, 1, l); }
	void edt(int l, int r, int id, int ql, int qr, int v) {
		if(r <= ql || qr <= l)
			return;
		if(ql <= l && r <= qr) {
			arr[id] += v;
			tag[id] += v;
			return;
		}
		push(id);
		int m = l + r >> 1;
		edt(l, m, id << 1, ql, qr, v);
		edt(m, r, id << 1 | 1, ql, qr, v);
		pull(id);
	}
	inline void edt(int l, int r, int v) { edt(0, n, 1, l, r, v); }
} tree;

signed main() { EMT
	int n;
	cin >> n;
	vector<int> arr(n + 1);
	for(int i = 0; i < n; i++)
		cin >> arr[i];
	tree.init(arr);
	int it = 0, ans = 0;
	while(it < n) {
		if(!tree.que(it, it + 1)) {
			it++;
			continue;
		}
		int w = tree.get(it);
		int m = tree.que(it, w);
		tree.edt(it, w, -m);
		ans++;
	}
	cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::build(int, int, int, std::vector<int>&)':
Main.cpp:31:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   int m = l + r >> 1;
      |           ~~^~~
Main.cpp: In member function 'int segtree::que(int, int, int, int, int)':
Main.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int m = l + r >> 1;
      |           ~~^~~
Main.cpp: In member function 'int segtree::get(int, int, int, int)':
Main.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |   int m = l + r >> 1;
      |           ~~^~~
Main.cpp: In member function 'void segtree::edt(int, int, int, int, int, int)':
Main.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int m = l + r >> 1;
      |           ~~^~~

• Subtask 1: 70 / 70