Submission #766176

#	Time	Username	Problem	Language	Result	Execution time	Memory
766176		Tenis0206	A Game with Grundy (CCO20_day1problem1)	C++11	0 / 25	13 ms	15956 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5;
const int dif = 1e6 + 1;

int n,l,r,y;

vector<pair<int,int>> eves;

int rez[nmax + 5];

int fr[2 * dif + 5];

int pint(double x)
{
    if(x >= 0)
    {
        return (int)(x);
    }
    return (int)(x) - 1;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n;
    cin>>l>>r>>y;
    for(int i=1; i<=n; i++)
    {
        int x,v,h;
        cin>>x>>v>>h;
        long double st = 1.0 * y * (1.0 * -h / v) + x;
        long double dr = 1.0 * y * (1.0 * h / v) + x;
        if(st > r || dr < l)
        {
            continue;
        }
        int st_ev = pint(st) + 1;
        int dr_ev = 0;
        if(pint(dr)==dr)
        {
            dr_ev = pint(dr);
        }
        else
        {
            dr_ev = pint(dr) + 1;
        }
        if(st_ev < l)
        {
            st_ev = l;
        }
        if(dr_ev > r)
        {
            dr_ev = r + 1;
        }
       // eves.push_back({st_ev,+1});
       // eves.push_back({dr_ev,-1});
       fr[st_ev + dif]++;
       fr[dr_ev + dif]--;
    }
    for(int i=1;i<=1e6 + dif;i++)
    {
        fr[i] += fr[i - 1];
        if(l + dif <= i && i <= r + dif)
        {
            ++rez[fr[i]];
        }
    }
   /* sort(eves.begin(),eves.end());
    int last = l;
    int cur = 0;
    for(auto it : eves)
    {
        int poz = it.first;
        int val = it.second;
        rez[cur] += poz - last;
        cur += val;
        last = poz;
    }
    rez[cur] += r - last + 1;
    */
    for(int i=0;i<=n;i++)
    {
        if(i)
        {
            rez[i] += rez[i - 1];
        }
        cout<<rez[i]<<'\n';
    }
    return 0;
}

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