Submission #989130

#	Time	Username	Problem	Language	Result	Execution time	Memory
989130		arya_nazari_	A Game with Grundy (CCO20_day1problem1)	C++14	0 / 25	58 ms	14804 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false);
#define ll long long
#define pii pair<ll, ll>
#define F first
#define S second
#define pb push_back
#define SZ(x) ((ll)(x).size())

const int N = 2e5+100;
ll n, l, r, x[N], ans[N];
long double v[N], h[N], y;
vector<pii> vec;

ll left(long double x) {
    if (int(x) == x) return x;
    if (x > 0) return int(x) + 1;
    return int(x);
}

ll right(long double x) {
    if (int(x) == x) return x+1;
    if (x > 0) return int(x) + 1;
    return int(x);
}

int main()
{
    sui
    cin >> n >> l >> r >> y;
    ll open = 0;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> v[i] >> h[i];
        long double m = v[i] / h[i];
        if (m == 0) {
            open++;
            continue;
        }
        long double x1 = y/m + x[i];
        long double x2 = y/(-m) + x[i];

        if (left(x1) < (r+1))
            vec.pb({left(x1), 0});
        if (right(x2) > l)
            vec.pb({right(x2), 1});
        else open ++;

        //cout << right(x2) << " " << left(x1) << endl;
    }

    vec.pb({l, 0});
    vec.pb({r+1, 0});


    sort(vec.begin(), vec.end());
    //for (auto u: vec) cout << u.F << " " << u.S << endl;

    for (int i = 1; i < SZ(vec); i++) {
        ll st = vec[i-1].F, ft = vec[i].F;
        
        ans[open] += ft - st;

        if (vec[i].S) open++;
        else open --;
    }

    ll s = 0;

    for (int i = 0; i <= n; i++) {
        s += ans[i];
        cout << s << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10