Submission #697739

#	Time	Username	Problem	Language	Result	Execution time	Memory
697739		winthemcut3	A Game with Grundy (CCO20_day1problem1)	C++14	0 / 25	8 ms	8020 KiB

Main

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
#define f(x) f[int((x)+mxM+2)]
using namespace std;

/** END OF TEMPLATE **/

const int mxM = 1e6 + 2;
const int mxN = 1e5 + 5;
ll n, L, R, Y;
int f[mxM*2 + 10], num[mxN];
void update(ll x, ll v, ll h) {
    ll b = -(x*v);
    long double X = -(Y+b)*h;
    X = floor(1.0*X/v); X++;
    ll rX = x + (x - X) + 1;
    if(X < -mxM) X = -mxM;
    if(rX > mxM) rX = mxM;
    f(X)++; f(rX)--;
}

int main()
{
    //FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n >> L >> R >> Y;
    FOR(i, 1, n) {
        ll x, v, h; cin >> x >> v >> h;
        update(x, v, h);
    }
    FOR(i, -1e6, 1e6) f(i) += f(i-1);
    FOR(i, L, R) if(f(i) <= n) num[f(i)]++;
    FOR(i, 1, n) num[i] += num[i-1];
    FOR(i, 0, n) cout << num[i] << ' ';

    return 0;
}

/*
y = 2/3x
3 => x =
y = 2x
y = ax + b
y = 2x + 8
3 + 8 = 2x


y = 2x - 8
y = 2x + 8
y = v/hx - b;
y + b = v/hx
=> x = ((y+b)/v)*h
*/

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