Submission #1312815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312815		aaaaaaaa	Po (COCI21_po)	C++20	30 / 70	249 ms	6692 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
struct segment_tree{
	vector<int> seg, lazy;
	int N;
	void init(int n){
		seg.resize(n * 4);
		lazy.resize(n * 4, 0);
		N = n;
	}
	void push(int node, int start, int end){
		if(lazy[node] == 0) return;
		seg[node] += lazy[node];
		if(start ^ end){
			lazy[node * 2 + 1] += lazy[node];
			lazy[node * 2 + 2] += lazy[node];
		}
		lazy[node] = 0;
	}
	void pull(int node){
		seg[node] = min(seg[node * 2 + 1], seg[node * 2 + 2]);
	}
	void update(int node, int start, int end, int l, int r, int x){
		push(node, start, end);
		if(start > r || end < l) return;
		if(start >= l && end <= r){
			lazy[node] = x;
			push(node, start, end);
			return;
		}
		int mid = start + (end - start) / 2;
		update(node * 2 + 1, start, mid, l, r, x);
		update(node * 2 + 2,  mid + 1, end, l, r, x);
		pull(node);
	}
	void update(int node, int start, int end, int idx, int v){
		push(node, start, end);
		if(start == end){
			seg[node] = v;
			return;
		}
		int mid = start + (end - start) / 2;
		if(idx <= mid) update(node * 2 + 1, start, mid, idx, v);
		else update(node * 2 + 2, mid + 1, end, idx, v);
		pull(node);
	}
	int query(int node, int start, int end, int l, int r){
		push(node, start, end);
		if(start > r || end < l) return inf;
		if(start >= l && end <= r) return seg[node];
		int mid = start + (end - start) / 2;
		return min(query(node * 2 + 1, start, mid, l, r), query(node * 2 + 2, mid + 1, end, l, r));
	}
	int query(int l, int r){
		return query(0, 1, N, l, r);
	}
	void update(int idx, int v){
		update(0, 1, N, idx, v);
	}
	void update(int l, int r, int v){
		update(0, 1, N, l, r, v);
	}
} tr;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, ans = 0;
    cin >> n; tr.init(n);
    for(int i = 1, x; i <= n; ++i){
        cin >> x;
        tr.update(i, x);
    }
    for(int i = 1; i <= n; ++i){
        int cur = tr.query(i, i);
        if(cur == 0) continue;
        ans += 1;
        int st = i, en = n, best = i;
        while(st <= en){
            int mid = st + (en - st) / 2;
            if(tr.query(i, mid) >= cur){
                st = mid + 1;
                best = mid;
            }else{
                en = mid - 1;
            }
        }
        tr.update(i, best, -cur);
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 30 / 70