Submission #1159774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159774		gohchingjayk	Janjetina (COCI21_janjetina)	C++20	0 / 110	352 ms	589824 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
constexpr int INF = 1ull << 60;

int w[100000 + 5];
int N, K;

struct Node {
	Node *left = nullptr, *right = nullptr;
	int l, r;
	//int val;
	
	Node(int a, int b) {
		l = a, r = b;
		if (l == r) {
			//val = w[l];
		}
		else {
			left = new Node(l, (l+r)>>1);
			right = new Node(((l+r)>>1) + 1, r);
			//val = max(left->val, right->val);
		}
	}
	
	int rmq(int start) {
		
		if (r < start) return 0;
		if (start <= l) {
			int len = r - start + 1;
			if (w[l] - len >= K) return r - l + 1;
			if (l == r) return 0;
			return left->rmq(start) + right->rmq(start);
		}
		return left->rmq(start) + right->rmq(start);
	}
};

Node *segtree;
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> K;
	
	for (int i = 0; i < N - 1; ++i) {
		cin >> w[i] >> w[i] >> w[i];
	}

	segtree = new Node(0, N - 2);

	int cnt = 0;
	for (int i = 0; i < N - 1; ++i) {
		cnt += segtree->rmq(i) * 2;
	}
	cout << cnt;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60