Submission #402546

#	Time	Username	Problem	Language	Result	Execution time	Memory
402546		penguinhacker	A Game with Grundy (CCO20_day1problem1)	C++14	25 / 25	72 ms	4876 KiB

Main

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

#define ll long long
#define ar array

const int mxN=1e5;
int n, a, b, y, ans[mxN+1];
ar<int, 2> e[2*mxN+1];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> a >> b >> y;
	for (int i=0; i<n; ++i) {
		ll x, v, h;
		cin >> x >> v >> h;
		ll w=(y*h-1)/v;
		// [x-w, x+w]
		int l=max((ll)a, x-w);
		int r=min((ll)b, x+w);
		e[2*i]={l, 1};
		e[2*i+1]={r+1, -1};
	}
	sort(e, e+2*n);
	e[2*n]={b+1, 0};
	int last=a, cur=0;
	for (int i=0; i<=2*n; ++i) {
		int x=e[i][0], inc=e[i][1];
		ans[cur]+=x-last, last=x, cur+=inc;
	}
	for (int i=0; i<=n; ++i) {
		ans[i]+=i?ans[i-1]:0;
		cout << ans[i] << "\n";
	}
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10