oj.uz

Submission #902241

# Submission time Handle Problem Language Result Execution time Memory
902241 2024-01-10T07:29:03 Z pcc A Game with Grundy (CCO20_day1problem1) C++14
25 / 25
 105 ms 7448 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e5+10;
const ll inf = 2e9+10;
int cnt[mxn*2];
int ans[mxn];
vector<ll> all;
pll range[mxn];
ll N,L,R,Y;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>L>>R>>Y;
	for(int i = 0;i<N;i++){
		ll a,b,x;
		cin>>x>>a>>b;
		ll l = -inf,r = inf;
		while(l != r){
			ll mid = l+(r-l)/2;
			if((x-mid)*a<Y*b)r = mid;
			else l = mid+1;
		}
		range[i].fs = l;
		l = -inf,r = inf;
		while(l != r){
			ll mid = l+(r-l+1)/2;
			if((mid-x)*a<Y*b)l = mid;
			else r = mid-1;
		}
		range[i].sc = r+1;
		all.push_back(range[i].fs);
		all.push_back(range[i].sc);
	}
	all.push_back(L);
	all.push_back(R+1);
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	for(int i = 0;i<N;i++){
		int l = lower_bound(all.begin(),all.end(),range[i].fs)-all.begin();
		int r = lower_bound(all.begin(),all.end(),range[i].sc)-all.begin();
		cnt[l]++,cnt[r]--;
	}
	int sum = 0;
	for(int i = 0;i+1<all.size();i++){
		sum += cnt[i];
		ans[sum] += max(min(R+1,all[i+1])-max(L,all[i]),0ll);
	}
	for(int i = 0;i<=N;i++){
		if(i)ans[i] += ans[i-1];
		cout<<ans[i]<<'\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 0;i+1<all.size();i++){
      |                ~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 85 ms 6384 KB Output is correct
4 Correct 104 ms 6796 KB Output is correct
5 Correct 92 ms 6724 KB Output is correct
6 Correct 90 ms 6344 KB Output is correct
7 Correct 58 ms 5852 KB Output is correct
8 Correct 1 ms 2404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 85 ms 6384 KB Output is correct
4 Correct 104 ms 6796 KB Output is correct
5 Correct 92 ms 6724 KB Output is correct
6 Correct 90 ms 6344 KB Output is correct
7 Correct 58 ms 5852 KB Output is correct
8 Correct 1 ms 2404 KB Output is correct
9 Correct 103 ms 7244 KB Output is correct
10 Correct 95 ms 7376 KB Output is correct
11 Correct 105 ms 7448 KB Output is correct
12 Correct 102 ms 7220 KB Output is correct
13 Correct 65 ms 6348 KB Output is correct