oj.uz

Submission #1106748

# Submission time Handle Problem Language Result Execution time Memory
1106748 2024-10-31T02:37:45 Z Math4Life2020 A Game with Grundy (CCO20_day1problem1) C++17
25 / 25
 79 ms 5560 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,fma,popcnt,lzcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;

int main() {
	ll N; cin >> N;
	ll L,R,Y; cin >> L >> R >> Y;
	vector<pii> upd;
	for (ll i=0;i<N;i++) {
		ll x,v,h; cin >> x >> v >> h;
		ll xmin = max(L,x-((h*Y-1)/v));
		ll xmax = min(R,x+((h*Y-1)/v));
		if (xmin>R) {
			continue;
		}
		if (xmax<L) {
			continue;
		}
		upd.push_back({xmin,1});
		upd.push_back({xmax+1,-1});
	}
	upd.push_back({R+1,0});
	sort(upd.begin(),upd.end());
	ll vc = 0; ll xc = L;
	ll updv[N+1];
	for (ll i=0;i<=N;i++) {
		updv[i]=0;
	}
	for (pii p0: upd) {
		ll x = p0.first; ll uv = p0.second;
		updv[vc]+=(x-xc);
		xc=x; vc+=uv;
	}
	for (ll i=1;i<=N;i++) {
		updv[i]+=updv[i-1];
	}
	for (ll i=0;i<=N;i++) {
		cout << updv[i]<<"\n";
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 68 ms 4684 KB Output is correct
4 Correct 71 ms 5048 KB Output is correct
5 Correct 68 ms 4900 KB Output is correct
6 Correct 73 ms 4548 KB Output is correct
7 Correct 53 ms 4536 KB Output is correct
8 Correct 1 ms 336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 68 ms 4684 KB Output is correct
4 Correct 71 ms 5048 KB Output is correct
5 Correct 68 ms 4900 KB Output is correct
6 Correct 73 ms 4548 KB Output is correct
7 Correct 53 ms 4536 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 74 ms 5304 KB Output is correct
10 Correct 73 ms 5560 KB Output is correct
11 Correct 79 ms 5560 KB Output is correct
12 Correct 74 ms 5488 KB Output is correct
13 Correct 55 ms 4656 KB Output is correct