제출 #1345294

#제출 시각아이디문제언어결과실행 시간메모리
1345294tvgkA Game with Grundy (CCO20_day1problem1)C++20
25 / 25
98 ms12848 KiB
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;

int ans[mxN], n;
ll l, r, y;
vector<ll> pivot;
map<int, int> mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    cin >> l >> r >> y;
    pivot.push_back(l);
    pivot.push_back(r + 1);
    for (int i = 1; i <= n; i++)
    {
        ll x, v, h;
        cin >> x >> h >> v;

        ll sum = (v * y - 1) / h;
        pivot.push_back(min(r + 1, sum + x + 1));
        mp[sum + x + 1]--;

        pivot.push_back(max(l, x - sum));
        mp[max(l, x - sum)]++;
    }
    sort(pivot.begin(), pivot.end());
    pivot.erase(unique(pivot.begin(), pivot.end()), pivot.end());

    int cnt = 0;
    for (int i = 0; i < pivot.size() - 1; i++)
    {
        cnt += mp[pivot[i]];
        ans[cnt] += pivot[i + 1] - pivot[i];

        //cerr << "SEG " << cnt << " " << pivot[i] << " " << pivot[i + 1] << '\n';
    }

    for (int i = 0; i <= n; i++)
    {
        if (i)
            ans[i] += ans[i - 1];
        cout << ans[i] << '\n';
    }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...