oj.uz

Submission #547642

# Submission time Handle Problem Language Result Execution time Memory
547642 2022-04-11T06:55:12 Z amunduzbaev A Game with Grundy (CCO20_day1problem1) C++17
25 / 25
 69 ms 4932 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 65 ms 4156 KB Output is correct
4 Correct 69 ms 4228 KB Output is correct
5 Correct 54 ms 4232 KB Output is correct
6 Correct 52 ms 3752 KB Output is correct
7 Correct 48 ms 3808 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 65 ms 4156 KB Output is correct
4 Correct 69 ms 4228 KB Output is correct
5 Correct 54 ms 4232 KB Output is correct
6 Correct 52 ms 3752 KB Output is correct
7 Correct 48 ms 3808 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 55 ms 4764 KB Output is correct
10 Correct 58 ms 4932 KB Output is correct
11 Correct 56 ms 4852 KB Output is correct
12 Correct 64 ms 4708 KB Output is correct
13 Correct 55 ms 4152 KB Output is correct