Submission #260715

#	Time	Username	Problem	Language	Result	Execution time	Memory
260715		ChrisT	A Game with Grundy (CCO20_day1problem1)	C++17	25 / 25	118 ms	10072 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#define int ll
const int MN = 1e5 + 5, MOD = 1e9 + 7, BASE = 131;
const ld EPS = 1e-8;
struct Event {
	ld x;int add;
};
int32_t main () {
	int n;
	scanf ("%lld",&n);
	int l,r,y;
	scanf ("%lld %lld %lld",&l,&r,&y);
	vector<Event> events;
	for (int i = 0; i < n; i++) {
		int x,v,h;
		scanf ("%lld %lld %lld",&x,&v,&h);
		ld lx = (ld)h/v * y + x;
		ld rx = -(ld)h/v * y + x;
		events.push_back({rx,1}); events.push_back({lx,-1}); 
//		printf ("%.5Lf 1 -- %.5Lf -1\n",rx,lx);
	}
	vector<int> ans(n+1);
	sort(all(events),[&](const Event &a, const Event &b) {return a.x < b.x || (a.x == b.x && a.add < b.add);});
	while (events.back().x > r) events.pop_back();
//	printf ("%.5Lf\n",events.back().x);
	int lst = l-1, cnt = 0;
	//<= that point, > lst
	for (Event &e : events) {
		int bef = (int)floorl(e.x);
		if (abs(e.x-roundl(e.x)) < EPS) bef = (int)roundl(e.x);
		if (e.add == -1 && abs(e.x-bef) <= EPS) --bef;
		bef = min(bef,r);
		if (bef >= lst) {
			ans[cnt] += bef - lst;
			lst = bef;
		}
		cnt += e.add;
	}
	ans[cnt] += r-lst;
	for (int i = 1; i <= n; i++) ans[i] += ans[i-1];
	for (int i = 0; i <= n; i++) printf ("%lld\n",ans[i]);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf ("%lld",&n);
      |  ~~~~~~^~~~~~~~~~~
Main.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |  scanf ("%lld %lld %lld",&l,&r,&y);
      |  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |   scanf ("%lld %lld %lld",&x,&v,&h);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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