萌新刚学OI求助

Cesare @ 2019-06-05 20:08:54

by Cesare @ 2019-06-05 20:09:17

#include <bits/stdc++.h>
//#include <tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define lll bignum
#define lowbit(x) ( x & -x )
#define debug(x) (cout << "#x = " << (x) << endl)
#define Set(x, i) memset (x, i, sizeof(x))
#define re register
#define For(i, j, k) for(re int i = (j); i <= (k); ++i)
#define foR(i, j, k) for(re int i = (j); i >= (k); --i)
#define Cross(i, j, k) for(re int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll N = 200011, M = N * 10;
const ll INF = 5e16;

ll Limit, Tong[M];
ll n, m, S, w[N], v[N], l[N], r[N];

namespace IO {

    inline char gc() {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return (p1 == p2) && (p2 = (p1 = buf) +
            fread (buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
    }

    #define dd ch = getchar()
    inline ll read() {
        ll x = 0; bool f = 0; char dd;
        for (; !isdigit (ch); dd) f ^= (ch == '-');
        for (; isdigit (ch); dd)  x = x * 10 + (ch ^ 48);
        return f? -x: x;
    }
    #undef dd

    inline void write( ll x ) {
        if (x < 0) putchar ('-'), x = -x;
        if (x > 9) write (x / 10); putchar (x % 10 | 48);
    }

    inline void wrn ( ll x ) { write (x); putchar (' '); }

    inline void wln ( ll x ) { write (x); putchar ('\n'); }

    inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); }

}

using namespace IO;

namespace Subtask1 {

    ll Odd = INF;

    void main () {
        For ( W, 1, Limit ) {
            ll Ans = 0;
            For ( i, 1, m ) {
                ll Cnt = 0, LL = Ans;
                For ( j, l[i], r[i] ) Cnt += (w[j] >= W);
                For ( j, l[i], r[i] ) Ans += Cnt * (w[j] >= W) * v[j];
            }
            Odd = min (Odd, abs (Ans - S));
        } wln (Odd), exit (0);
    }

}

namespace Subtask2 {

    ll W, SS, len, res = 0, Sum = 0, Ans = INF, cnt[M];

    struct MoTeam {
        ll l, r, id;
    } Q[N];

    inline bool cmp ( MoTeam a, MoTeam b ) {
        return (a.l / len ^ b.l / len)? 
            a.l < b.l: (a.l / len & 1)? a.r < b.r: a.r > b.r;
    }

    inline void add ( ll x ) {
        if (w[x] >= W) {
            ll Num = 0;
            if (SS != 0) Num = res / SS;
            SS += v[x];
            if (!Num) res += SS;
            else res = (Num + 1) * SS;
        }
    }

    inline void del ( ll x ) {
        if (w[x] >= W) {
            ll Num = 0;
            if (SS != 0) Num = res / SS;
            SS -= v[x];
            if (!Num) return ;
            res = (Num - 1) * SS;
        }
    }

    void main () {
        len = pow (n, 2.0 / 3.0);
        For ( i, 1, m ) 
            Q[i].l = l[i], Q[i].r = r[i], Q[i].id = i;

//      sort (Q + 1, Q + m + 1, cmp);
        for (W = 0; W <= Limit; ++W) {
            SS = 0;
            Sum = res = 0;
            ll L = 1, R = 0;
            For ( i, 1, m ) {
                if (Sum - S > Ans) break;
                while (L > Q[i].l) add (--L);
                while (L < Q[i].l) del (L++);
                while (R < Q[i].r) add (++R);
                while (R > Q[i].r) del (R--);
                Sum += res;
            }
            Ans = min (Ans, abs (Sum - S));
        } wln (Ans); exit (0);
    }

}

int main()
{
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    n = read(), m = read(), S = read();
    For ( i, 1, n ) w[i] = read(), v[i] = read();
    For ( i, 1, m ) l[i] = read(), r[i] = read();
    For ( i, 1, n ) Limit = max (Limit, w[i]);

    if (Limit * m * n <= 2e9) Subtask1::main ();

    Subtask2::main ();

    For ( i, 1, n ) ++Tong[w[i]];
    For ( i, 1, Limit ) Tong[i] += Tong[i - 1];
    return 0;
}

/*

*/

by Cesare @ 2019-06-05 20:16:01

@wycero

这次我在您来之前放代码了，所以您能帮我解答这个问题吗？

by South_Sky_Plume5 @ 2019-06-05 20:17:54

@Cesare 竟然是你

by Cesare @ 2019-06-05 20:18:43

@南天羽5 天线宝宝就不能学 OI 了吗

by 小菜鸟 @ 2019-06-05 20:24:21

海绵和海星都可以了，还有什么不行的

by Cesare @ 2019-06-05 20:38:55

本来还想优化这个玩意，结果这么氵

by Cesare @ 2019-06-05 20:53:21

算了吧改了二分写法优化最开始的暴力就过了

by South_Sky_Plume5 @ 2019-06-05 21:03:49

@Cesare 你们五个······

by shierjie @ 2019-06-05 21:24:07

@小菜鸟 鸟学OI的全都是巨佬（滑稽）

by ferrum_cccp @ 2019-06-06 20:50:48

这题不是二分吗