Submission #547642

#	Time	Username	Problem	Language	Result	Execution time	Memory
547642		amunduzbaev	A Game with Grundy (CCO20_day1problem1)	C++17	25 / 25	69 ms	4932 KiB

Main

#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const double eps = 1e-5;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	int l, r, y; cin>>l>>r>>y;
	vector<ar<int, 2>> tot;
	for(int i=0;i<n;i++){
		int x, u, v; cin>>x>>u>>v;
		ar<double, 2> s, b; 
		s[0] = u * 1. / v, s[1] = -s[0];
		b[0] = s[1] * x, b[1] = -b[0];
		double L = (y - b[0]) / s[0], R = (y - b[1]) / s[1];
		if(L - R > eps) swap(L, R);
		int l = ceil(L), r = floor(R);
		if(abs(l - L) < eps) l++;
		if(abs(r - R) < eps) r--;
		tot.push_back({l, 1});
		tot.push_back({++r, -1});
		//~ cout<<l<<" "<<r<<"\n";
	}
	
	tot.push_back({l, 0});
	tot.push_back({r + 1, 0});
	sort(tot.begin(), tot.end());
	vector<int> C(n + 1);
	for(int i=0, cnt=0, m=tot.size();i<m;){
		int j=i;
		while(j<m && tot[i][0] == tot[j][0]) cnt += tot[j][1], j++;
		if(l <= tot[i][0] && tot[i][0] <= r){
			assert(j<m);
			C[cnt] += tot[j][0] - tot[i][0];
		} i = j;
	}
	
	for(int i=0;i<=n;i++){
		if(i) C[i] += C[i-1];
		cout<<C[i]<<"\n";
	}
}

/*

3
-7 7 3
0 2 3
-4 2 1
3 3 1

*/

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