Submission #362719

#TimeUsernameProblemLanguageResultExecution timeMemory
362719alextodoranA Game with Grundy (CCO20_day1problem1)C++17
25 / 25
234 ms16364 KiB
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100002;

const double EPS = 1e-10;

int n;

ll L, R, Y;

long double getx (ll v, ll h, ll x)
{
    return x + (long double)Y * h / v;
}

map <ll, int> mp;

ll ans[N_MAX];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cin >> L >> R >> Y;
    for(int i = 1; i <= n; i++)
    {
        ll v, h, x;
        cin >> x >> v >> h;
        ll l = ceil(getx(-v, h, x) + EPS);
        ll r = floor(getx(v, h, x) - EPS);
        l = max(L, l);
        r = min(R, r);
        mp[l]++;
        mp[r + 1]--;
    }
    mp[R + 1];
    ll last = L;
    int cnt = 0;
    for(pair <ll, int> p : mp)
    {
        ans[cnt] += p.first - last;
        cnt += p.second;
        last = p.first;
    }
    for(int i = 1; i <= n; i++)
        ans[i] += ans[i - 1];
    for(int i = 0; i <= n; i++)
        cout << ans[i] << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...