oj.uz

Submission #574665

# Submission time Handle Problem Language Result Execution time Memory
574665 2022-06-09T07:15:44 Z balbit Bodyguard (JOI21_bodyguard) C++14
100 / 100
 7736 ms 1290400 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2800*2+5;

//ll xat[maxn], yat[maxn];
ll rt[maxn][maxn], dw[maxn][maxn]; // right (m++), down (n++)
ll dp[maxn][maxn];

struct seg{
    ll l,r,h,c;
};

vector<seg> dseg, rseg;
vector<ll> dax, rax; // axis lines

ll ans[3000005];
//struct ask{
//    signed df, i;
//};

vector<signed> ha[maxn][maxn];

bool QTYPE=0;
struct Line {
    mutable ll m, b, p;
    bool operator<(const Line& o) const {
        if (QTYPE) return p<o.p;
        return m < o.m;
    }
};

struct LineContainer : multiset<Line > {
    const ll INF = LLONG_MAX;
    ll div(ll A, ll B) {
        return A / B - ((A ^ B) < 0 && A % B); }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = INF; return false; }
        if (x->m == y->m) x->p = x->b > y->b ? INF : -INF;
        else x->p = div(y->b - x->b, x->m - y->m);
        return x->p >= y->p;}
    void add(ll m, ll b) {
        auto z = insert({m, b, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));}
    ll query(ll x) {
        assert(!empty());
        QTYPE=1; auto l = *lower_bound({0,0,x}); QTYPE = 0;
        return l.m * x + l.b; }
};


signed main(){
    IOS();

    int n,q; cin>>n>>q;

    REP(i,n) {
        int t,a,b,c; cin>>t>>a>>b>>c;
        if (a < b) {
            // down segment
            dseg.pb({t+a, t+b-a+b, t-a, c});
            bug("down", t-a, t+a, t+b-a+b);
            bug(c);
        }else{
            // right seg
            rseg.pb({t-a, t+(a-b)-b, t+a, c});
            bug("right", t+a, t-a, t+(a-b)-b);
            bug(c);
        }
    }
    for (auto s : dseg) {
        dax.pb(s.h);
        rax.pb(s.l);
        rax.pb(s.r);
    }
    for (auto s : rseg) {
        rax.pb(s.h);
        dax.pb(s.l);
        dax.pb(s.r);
    }

    SORT_UNIQUE(rax);
    SORT_UNIQUE(dax);

    auto getr = [&](ll x) {return lower_bound(ALL(rax), x) - rax.begin();};
    auto getd = [&](ll x) {return lower_bound(ALL(dax), x) - dax.begin();};

    for (auto s : dseg) {
        // work on dw array
        int L = getr(s.l), R = getr(s.r);
        int H = getd(s.h);
        for (int i = L; i<R; ++i) {
            MX(dw[i][H], s.c);
        }
    }

    for (auto s : rseg) {
        // work on rt array
        int L = getd(s.l), R = getd(s.r);
        int H = getr(s.h);
        for (int i = L; i<R; ++i) {
            MX(rt[H][i], s.c);
        }
    }

    int N = SZ(rax), M = SZ(dax);

    for (int i = N-1; i>=0; --i) for (int j = M-1; j>=0; --j) {
        if (i + 1 < N) {
            MX(dp[i][j], dp[i+1][j] + (rax[i+1] - rax[i])*dw[i][j]);
        }
        if (j + 1 < M) {
            MX(dp[i][j], dp[i][j+1] + (dax[j+1] - dax[j])*rt[i][j]);
        }
        bug(i,j,rax[i],dax[j],dp[i][j]);
    }

    vector<int> qR(q), qC(q);

    REP(i, q) {
        int t,x; cin>>t>>x;
        int r = t+x, c = t-x;
        tie(qR[i], qC[i]) = {r,c};
        int dpos = getd(c), rpos = getr(r);
        if (dpos >= M || rpos >= N) continue;
        bug(r,c,dpos,rpos);
        ha[rpos][dpos].pb(i);
//        dask[rpos][dpos].pb({dax[dpos] - c, i});
//        rask[rpos][dpos].pb({rax[rpos] - r, i});
    }

    REP(i,N) {
        LineContainer hull;
        for (int j = M-1; j>=0; --j) {
            hull.add(i?dw[i-1][j]:0, dp[i][j]);
            for (int it : ha[i][j]) {
                int df = rax[i] - qR[it];
//                bug(aa.i, aa.df, hull.query(aa.df));
                MX(ans[it], hull.query(df));
            }
        }
    }

    REP(j,M) {
        LineContainer hull;
        for (int i = N-1; i>=0; --i) {
            hull.add(j?rt[i][j-1]:0, dp[i][j]);
            for (int it : ha[i][j]) {
                int df = dax[j] - qC[it];
//                bug(aa.i, aa.df, hull.query(aa.df));
                MX(ans[it], hull.query(df));
            }
        }
    }


    REP(i,q) {
        cout<<ans[i]/2<<endl;
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5386 ms 1070948 KB Output is correct
2 Correct 5384 ms 1070640 KB Output is correct
3 Correct 2021 ms 913060 KB Output is correct
4 Correct 1456 ms 844552 KB Output is correct
5 Correct 4116 ms 1127428 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3472 ms 1040192 KB Output is correct
2 Correct 3611 ms 1039572 KB Output is correct
3 Correct 3234 ms 1043644 KB Output is correct
4 Correct 352 ms 738564 KB Output is correct
5 Correct 3180 ms 977684 KB Output is correct
6 Correct 3205 ms 947132 KB Output is correct
7 Correct 3054 ms 977352 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3472 ms 1040192 KB Output is correct
2 Correct 3611 ms 1039572 KB Output is correct
3 Correct 3234 ms 1043644 KB Output is correct
4 Correct 352 ms 738564 KB Output is correct
5 Correct 3180 ms 977684 KB Output is correct
6 Correct 3205 ms 947132 KB Output is correct
7 Correct 3054 ms 977352 KB Output is correct
8 Correct 3406 ms 1040076 KB Output is correct
9 Correct 3291 ms 1039892 KB Output is correct
10 Correct 3131 ms 1042732 KB Output is correct
11 Correct 355 ms 738684 KB Output is correct
12 Correct 2961 ms 977876 KB Output is correct
13 Correct 2956 ms 947232 KB Output is correct
14 Correct 3166 ms 977828 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3472 ms 1040192 KB Output is correct
2 Correct 3611 ms 1039572 KB Output is correct
3 Correct 3234 ms 1043644 KB Output is correct
4 Correct 352 ms 738564 KB Output is correct
5 Correct 3180 ms 977684 KB Output is correct
6 Correct 3205 ms 947132 KB Output is correct
7 Correct 3054 ms 977352 KB Output is correct
8 Correct 3406 ms 1040076 KB Output is correct
9 Correct 3291 ms 1039892 KB Output is correct
10 Correct 3131 ms 1042732 KB Output is correct
11 Correct 355 ms 738684 KB Output is correct
12 Correct 2961 ms 977876 KB Output is correct
13 Correct 2956 ms 947232 KB Output is correct
14 Correct 3166 ms 977828 KB Output is correct
15 Correct 3258 ms 1043624 KB Output is correct
16 Correct 3279 ms 1043956 KB Output is correct
17 Correct 3190 ms 1046820 KB Output is correct
18 Correct 367 ms 740568 KB Output is correct
19 Correct 3019 ms 979904 KB Output is correct
20 Correct 2990 ms 949392 KB Output is correct
21 Correct 3194 ms 979848 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5386 ms 1070948 KB Output is correct
2 Correct 5384 ms 1070640 KB Output is correct
3 Correct 2021 ms 913060 KB Output is correct
4 Correct 1456 ms 844552 KB Output is correct
5 Correct 4116 ms 1127428 KB Output is correct
6 Correct 3472 ms 1040192 KB Output is correct
7 Correct 3611 ms 1039572 KB Output is correct
8 Correct 3234 ms 1043644 KB Output is correct
9 Correct 352 ms 738564 KB Output is correct
10 Correct 3180 ms 977684 KB Output is correct
11 Correct 3205 ms 947132 KB Output is correct
12 Correct 3054 ms 977352 KB Output is correct
13 Correct 3406 ms 1040076 KB Output is correct
14 Correct 3291 ms 1039892 KB Output is correct
15 Correct 3131 ms 1042732 KB Output is correct
16 Correct 355 ms 738684 KB Output is correct
17 Correct 2961 ms 977876 KB Output is correct
18 Correct 2956 ms 947232 KB Output is correct
19 Correct 3166 ms 977828 KB Output is correct
20 Correct 3258 ms 1043624 KB Output is correct
21 Correct 3279 ms 1043956 KB Output is correct
22 Correct 3190 ms 1046820 KB Output is correct
23 Correct 367 ms 740568 KB Output is correct
24 Correct 3019 ms 979904 KB Output is correct
25 Correct 2990 ms 949392 KB Output is correct
26 Correct 3194 ms 979848 KB Output is correct
27 Correct 7736 ms 1290400 KB Output is correct
28 Correct 7071 ms 1285132 KB Output is correct
29 Correct 4995 ms 1230176 KB Output is correct
30 Correct 1429 ms 887796 KB Output is correct
31 Correct 4445 ms 1085732 KB Output is correct
32 Correct 4873 ms 1118516 KB Output is correct
33 Correct 4029 ms 1132892 KB Output is correct