MENU

Tyvj2065 「Poetize10」封印一击

Tyvj2065

E只可能是某个端点,按位置枚举所有端点,更新答案。

#include<cstdio>
#include<algorithm>
#ifdef WIN32
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#else
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define inline __attribute__((always_inline))
#endif
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void putc(char x) {
        *oS++ = x;
        if (oS == oT)fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
    }
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T>T rd() {
        int c = gc();
        T x = 0;
        for (; c < 48; c = gc());
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if (!x) { putc('0'); return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {
#ifndef ONLINE_JUDGE
        freopen("seal.in", "r", stdin), freopen("seal.out", "w", stdout);
#endif
    }
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int N = ip.rd<int>(), cnt, mx;
long long sum, ans;
struct abcd {
    int x, opt;
    abcd(int x = 0, int opt = 0) :x(x), opt(opt) {}
}node[200001];
inline bool operator<(abcd a, abcd b) { return a.x != b.x ? a.x < b.x : a.opt < b.opt; }
int main() {
    for (int i = 1; i <= N; ++i) {
        int a = ip.rd<int>();
        sum += a, node[i] = abcd(a, 1), node[N + i] = abcd(ip.rd<int>(), 0);
    }
    N <<= 1, std::sort(node + 1, node + N + 1);
    for (int i = 1; i <= N; ++i) {
        abcd t = node[i];
        if (t.opt) {
            sum -= t.x, ++cnt;
            long long temp;
            if (ans < (temp = sum + (long long)cnt * t.x)) ans = temp, mx = t.x;
        }
        else {
            long long temp;
            if (ans < (temp = sum + (long long)cnt * t.x)) ans = temp, mx = t.x;
            --cnt;
        }
    }
    ip.print(mx), ip.putc(' '), ip.print(ans);
}