Submission #1106748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106748		Math4Life2020	A Game with Grundy (CCO20_day1problem1)	C++17	25 / 25	79 ms	5560 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,fma,popcnt,lzcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;

int main() {
	ll N; cin >> N;
	ll L,R,Y; cin >> L >> R >> Y;
	vector<pii> upd;
	for (ll i=0;i<N;i++) {
		ll x,v,h; cin >> x >> v >> h;
		ll xmin = max(L,x-((h*Y-1)/v));
		ll xmax = min(R,x+((h*Y-1)/v));
		if (xmin>R) {
			continue;
		}
		if (xmax<L) {
			continue;
		}
		upd.push_back({xmin,1});
		upd.push_back({xmax+1,-1});
	}
	upd.push_back({R+1,0});
	sort(upd.begin(),upd.end());
	ll vc = 0; ll xc = L;
	ll updv[N+1];
	for (ll i=0;i<=N;i++) {
		updv[i]=0;
	}
	for (pii p0: upd) {
		ll x = p0.first; ll uv = p0.second;
		updv[vc]+=(x-xc);
		xc=x; vc+=uv;
	}
	for (ll i=1;i<=N;i++) {
		updv[i]+=updv[i-1];
	}
	for (ll i=0;i<=N;i++) {
		cout << updv[i]<<"\n";
	}
}

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