Codeforces 912C Perun, Ult!

Perun, Ult!

恶心题， 好多细节。。。 啊， 好恶心啊。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

const double eps = 1e-;

const double PI = acos(-);

int n, m;

vector<PLL> vc[N];

vector<LL> prefix[N];

vector<LL> gg;

LL bou, inc, dam;

LL maxh[N], starth[N], regen[N];

vector<LL> oo;

vector<LL> cnt;

vector<PLL> add;

int getPos(LL x) {

    return lower_bound(oo.begin(), oo.end(), x) - oo.begin();

}

int main() {

    scanf("%d%d", &n, &m);

    scanf("%lld%lld%lld", &bou, &inc, &dam);

    for(int i = ; i <= n; i++) {

        scanf("%lld%lld%lld", &maxh[i], &starth[i], &regen[i]);

        vc[i].push_back(mk(, starth[i]));

    }

    for(int i = ; i <= m; i++) {

        LL x, y, z; scanf("%lld%lld%lld", &x, &y, &z);

        vc[y].push_back(mk(x, z));

    }

    for(int i = ; i <= n; i++) {

        if(maxh[i] <= dam && inc) {

            puts("-1");

            return ;

        }

    }

    for(int i = ; i <= n; i++) sort(vc[i].begin(), vc[i].end());

    for(int i = ; i <= n; i++) {

        for(int j = ; j < SZ(vc[i]); j++) {

            LL up = j < SZ(vc[i]) -  ? vc[i][j + ].fi -  : INF;

            if(vc[i][j].se > dam) continue;

            if(regen[i]) {

                LL ret = (dam - vc[i][j].se) / regen[i];

                add.push_back(mk(vc[i][j].fi, min(up, vc[i][j].fi + ret)));

                oo.push_back(vc[i][j].fi);

                oo.push_back(min(up, vc[i][j].fi + ret) + );

            } else {

                if(up == INF && inc) {

                    puts("-1");

                    return ;

                } else {

                    add.push_back(mk(vc[i][j].fi, up));

                    oo.push_back(vc[i][j].fi);

                    oo.push_back(up + );

                }

            }

        }

    }

    LL ans = ;

    sort(oo.begin(), oo.end());

    oo.erase(unique(oo.begin(), oo.end()), oo.end());

    cnt.resize(SZ(oo));

    for(auto& t : add) {

        cnt[getPos(t.fi)]++;

        cnt[getPos(t.se + )]--;

    }

    for(int i = ; i < SZ(cnt); i++) {

        if(i) cnt[i] += cnt[i - ];

        ans = max(ans, 1LL * cnt[i] * (bou + (oo[i + ] - ) * inc));

    }

    printf("%lld\n", ans);

    return ;

}

/*

*/