oj.uz

Submission #260715

# Submission time Handle Problem Language Result Execution time Memory
260715 2020-08-10T19:07:29 Z ChrisT A Game with Grundy (CCO20_day1problem1) C++17
25 / 25
 118 ms 10072 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 100 ms 9704 KB Output is correct
4 Correct 116 ms 9824 KB Output is correct
5 Correct 103 ms 9708 KB Output is correct
6 Correct 95 ms 9708 KB Output is correct
7 Correct 96 ms 9440 KB Output is correct
8 Correct 1 ms 372 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 100 ms 9704 KB Output is correct
4 Correct 116 ms 9824 KB Output is correct
5 Correct 103 ms 9708 KB Output is correct
6 Correct 95 ms 9708 KB Output is correct
7 Correct 96 ms 9440 KB Output is correct
8 Correct 1 ms 372 KB Output is correct
9 Correct 118 ms 9972 KB Output is correct
10 Correct 109 ms 10072 KB Output is correct
11 Correct 115 ms 10064 KB Output is correct
12 Correct 105 ms 9936 KB Output is correct
13 Correct 98 ms 9432 KB Output is correct