oj.uz

Submission #1069625

# Submission time Handle Problem Language Result Execution time Memory
1069625 2024-08-22T07:21:13 Z GrindMachine Tricks of the Trade (CEOI23_trade) C++17
50 / 100
 499 ms 39584 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
 
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
 
template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}
 
template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
/*
 
refs:
https://codeforces.com/blog/entry/98663 (max+ convolution tutorial)
https://judge.yosupo.jp/submission/166484 (max+ convolution implementation) 
 
*/
 
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<pll> max_conv(vector<ll> a, vector<pll> b){
    // a = concave, b = arbitrary
    ll n = sz(a), m = sz(b);
    vector<pll> res(n+m-1,{-inf2,-inf2});

    auto go = [&](ll l, ll r, ll optl, ll optr, auto &&go) -> void{
        if(l > r) return;
        ll mid = (l+r) >> 1;
        ll best = -inf2, optm = -1;
        for(int j = optl; j <= optr; ++j){
            ll i = mid-j;
            if(i >= 0 and i < n){
                ll val = a[i]+b[j].ff;
                if(val >= best){
                    best = val;
                    optm = j;
                }
            }
        }

        res[mid] = {best,b[optm].ss};
        go(l,mid-1,optl,optm,go);
        go(mid+1,r,optm,optr,go);
    };

    go(0,n+m-2,0,m-1,go);
    return res;
}

void solve(int test_case)
{
    ll n,k; cin >> n >> k;
    vector<ll> a(n+5), b(n+5);
    rep1(i,n) cin >> a[i];
    rep1(i,n) cin >> b[i];    
 
    ll ans = -inf2;
    vector<pll> segs;

    auto upd = [&](ll l, ll r, ll v){
        if(v > ans){
            ans = v;
            segs.clear();
            segs.pb({l,r});
        }
        else if(v == ans){
            segs.pb({l,r});
        }
    };

    auto go = [&](ll l, ll r, auto &&go) -> pair<vector<pll>,vector<pll>>{
        if(l > r) return {{{0,0}},{{0,0}}};
        if(l == r){
            vector<pll> v = {{0,0},{-a[l]+b[l],1}};
            return {v,v};
        }
    
        ll mid = (l+r) >> 1;
        auto [lp,ls] = go(l,mid,go);
        auto [rp,rs] = go(mid+1,r,go);
        ll siz = r-l+1;
 
        vector<pll> cp(siz+1,{-inf2,-inf2}), cs(siz+1,{-inf2,-inf2});
        rep(i,sz(lp)) amax(cp[i],lp[i]);
        rep(i,sz(rs)) amax(cs[i],rs[i]);
 
        {
            vector<ll> vals;
            ll sum = 0;
            for(int i = l; i <= mid; ++i){
                sum -= a[i];
                vals.pb(b[i]);
            }
 
            sort(rall(vals));
            vals.insert(vals.begin(),sum);
            rep1(i,sz(vals)-1) vals[i] += vals[i-1];

            auto res = max_conv(vals,rp);
            rep(i,sz(res)) res[i].ss += mid-l+1;
            rep(i,sz(res)) amax(cp[i],res[i]);
        }
 
        {
            vector<ll> vals;
            ll sum = 0;
            for(int i = mid+1; i <= r; ++i){
                sum -= a[i];
                vals.pb(b[i]);
            }
 
            sort(rall(vals));
            vals.insert(vals.begin(),sum);
            rep1(i,sz(vals)-1) vals[i] += vals[i-1];

            auto res = max_conv(vals,ls);
            rep(i,sz(res)) res[i].ss += r-mid;
            rep(i,sz(res)) amax(cs[i],res[i]);
        }
 
        if(k < sz(cp)) upd(l,l+cp[k].ss-1,cp[k].ff);
        if(k < sz(cs)) upd(r-cs[k].ss+1,r,cs[k].ff);
 
        rep(j,sz(ls)){
            ll p = k-j;
            if(p >= 0 and p < sz(rp)){
                ll lx = mid-ls[j].ss+1;
                ll rx = mid+1+rp[p].ss-1;
                ll val = ls[j].ff+rp[p].ff;
                upd(mid-ls[j].ss+1,mid+1+rp[p].ss-1,ls[j].ff+rp[p].ff);
            }
        }
    
        rep1(i,sz(cp)-1) assert(cp[i].ss >= cp[i-1].ss);
        rep1(i,sz(cs)-1) assert(cs[i].ss >= cs[i-1].ss);

        return {cp,cs};
    };

    go(1,n,go);
    cout << ans << endl;
}
 
int main()
{
    fastio;
 
    int t = 1;
    // cin >> t;
 
    rep1(i, t) {
        solve(i);
    }
 
    return 0;
}

Compilation message

trade.cpp: In instantiation of 'solve(int)::<lambda(ll, ll, auto:24&&)> [with auto:24 = solve(int)::<lambda(ll, ll, auto:24&&)>&; ll = long long int]':
trade.cpp:181:14:   required from here
trade.cpp:168:20: warning: unused variable 'lx' [-Wunused-variable]
  168 |                 ll lx = mid-ls[j].ss+1;
      |                    ^~
trade.cpp:169:20: warning: unused variable 'rx' [-Wunused-variable]
  169 |                 ll rx = mid+1+rp[p].ss-1;
      |                    ^~
trade.cpp:170:20: warning: unused variable 'val' [-Wunused-variable]
  170 |                 ll val = ls[j].ff+rp[p].ff;
      |                    ^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 0 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 0 ms 348 KB Partially correct
7 Partially correct 0 ms 348 KB Partially correct
8 Partially correct 1 ms 348 KB Partially correct
9 Partially correct 1 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 0 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 0 ms 348 KB Partially correct
7 Partially correct 0 ms 348 KB Partially correct
8 Partially correct 1 ms 348 KB Partially correct
9 Partially correct 1 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct
12 Partially correct 1 ms 348 KB Partially correct
13 Partially correct 0 ms 348 KB Partially correct
14 Partially correct 0 ms 344 KB Partially correct
15 Partially correct 0 ms 348 KB Partially correct
16 Partially correct 1 ms 348 KB Partially correct
17 Partially correct 0 ms 348 KB Partially correct
18 Partially correct 1 ms 344 KB Partially correct
19 Partially correct 1 ms 344 KB Partially correct
20 Partially correct 1 ms 348 KB Partially correct
21 Partially correct 0 ms 348 KB Partially correct
22 Partially correct 1 ms 348 KB Partially correct
23 Partially correct 7 ms 1116 KB Partially correct
24 Partially correct 7 ms 1116 KB Partially correct
25 Partially correct 9 ms 1112 KB Partially correct
26 Partially correct 8 ms 1116 KB Partially correct
27 Partially correct 5 ms 1116 KB Partially correct
28 Partially correct 7 ms 1132 KB Partially correct
29 Partially correct 8 ms 1116 KB Partially correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 290 ms 38332 KB Partially correct
3 Partially correct 359 ms 32372 KB Partially correct
4 Partially correct 287 ms 32368 KB Partially correct
5 Partially correct 327 ms 33580 KB Partially correct
6 Partially correct 373 ms 31800 KB Partially correct
7 Partially correct 418 ms 31304 KB Partially correct
8 Partially correct 380 ms 32180 KB Partially correct
9 Partially correct 348 ms 30716 KB Partially correct
10 Partially correct 360 ms 39500 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 290 ms 38332 KB Partially correct
3 Partially correct 359 ms 32372 KB Partially correct
4 Partially correct 287 ms 32368 KB Partially correct
5 Partially correct 327 ms 33580 KB Partially correct
6 Partially correct 373 ms 31800 KB Partially correct
7 Partially correct 418 ms 31304 KB Partially correct
8 Partially correct 380 ms 32180 KB Partially correct
9 Partially correct 348 ms 30716 KB Partially correct
10 Partially correct 360 ms 39500 KB Partially correct
11 Partially correct 1 ms 348 KB Partially correct
12 Partially correct 332 ms 39584 KB Partially correct
13 Partially correct 358 ms 32272 KB Partially correct
14 Partially correct 293 ms 32508 KB Partially correct
15 Partially correct 330 ms 33576 KB Partially correct
16 Partially correct 367 ms 31700 KB Partially correct
17 Partially correct 419 ms 31492 KB Partially correct
18 Partially correct 375 ms 32324 KB Partially correct
19 Partially correct 392 ms 30592 KB Partially correct
20 Partially correct 361 ms 39496 KB Partially correct
21 Partially correct 1 ms 512 KB Partially correct
22 Partially correct 1 ms 600 KB Partially correct
23 Partially correct 1 ms 348 KB Partially correct
24 Partially correct 1 ms 348 KB Partially correct
25 Partially correct 1 ms 348 KB Partially correct
26 Partially correct 1 ms 348 KB Partially correct
27 Partially correct 0 ms 348 KB Partially correct
28 Partially correct 0 ms 348 KB Partially correct
29 Partially correct 1 ms 348 KB Partially correct
30 Partially correct 0 ms 348 KB Partially correct
31 Partially correct 356 ms 32268 KB Partially correct
32 Partially correct 355 ms 32200 KB Partially correct
33 Partially correct 383 ms 31864 KB Partially correct
34 Partially correct 414 ms 35128 KB Partially correct
35 Partially correct 464 ms 32172 KB Partially correct
36 Partially correct 470 ms 30588 KB Partially correct
37 Partially correct 277 ms 36888 KB Partially correct

Subtask #5
25.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Partially correct 0 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 0 ms 348 KB Partially correct
7 Partially correct 1 ms 348 KB Partially correct
8 Partially correct 0 ms 348 KB Partially correct
9 Partially correct 0 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 1 ms 348 KB Partially correct
12 Partially correct 1 ms 348 KB Partially correct
13 Partially correct 0 ms 348 KB Partially correct
14 Partially correct 1 ms 348 KB Partially correct
15 Partially correct 0 ms 348 KB Partially correct
16 Partially correct 0 ms 344 KB Partially correct
17 Partially correct 0 ms 348 KB Partially correct
18 Partially correct 1 ms 348 KB Partially correct
19 Partially correct 0 ms 348 KB Partially correct
20 Partially correct 1 ms 344 KB Partially correct
21 Partially correct 1 ms 344 KB Partially correct
22 Partially correct 1 ms 348 KB Partially correct
23 Partially correct 0 ms 348 KB Partially correct
24 Partially correct 1 ms 348 KB Partially correct
25 Partially correct 7 ms 1116 KB Partially correct
26 Partially correct 7 ms 1116 KB Partially correct
27 Partially correct 9 ms 1112 KB Partially correct
28 Partially correct 8 ms 1116 KB Partially correct
29 Partially correct 5 ms 1116 KB Partially correct
30 Partially correct 7 ms 1132 KB Partially correct
31 Partially correct 8 ms 1116 KB Partially correct
32 Partially correct 0 ms 348 KB Partially correct
33 Partially correct 290 ms 38332 KB Partially correct
34 Partially correct 359 ms 32372 KB Partially correct
35 Partially correct 287 ms 32368 KB Partially correct
36 Partially correct 327 ms 33580 KB Partially correct
37 Partially correct 373 ms 31800 KB Partially correct
38 Partially correct 418 ms 31304 KB Partially correct
39 Partially correct 380 ms 32180 KB Partially correct
40 Partially correct 348 ms 30716 KB Partially correct
41 Partially correct 360 ms 39500 KB Partially correct
42 Partially correct 1 ms 348 KB Partially correct
43 Partially correct 332 ms 39584 KB Partially correct
44 Partially correct 358 ms 32272 KB Partially correct
45 Partially correct 293 ms 32508 KB Partially correct
46 Partially correct 330 ms 33576 KB Partially correct
47 Partially correct 367 ms 31700 KB Partially correct
48 Partially correct 419 ms 31492 KB Partially correct
49 Partially correct 375 ms 32324 KB Partially correct
50 Partially correct 392 ms 30592 KB Partially correct
51 Partially correct 361 ms 39496 KB Partially correct
52 Partially correct 1 ms 512 KB Partially correct
53 Partially correct 1 ms 600 KB Partially correct
54 Partially correct 1 ms 348 KB Partially correct
55 Partially correct 1 ms 348 KB Partially correct
56 Partially correct 1 ms 348 KB Partially correct
57 Partially correct 1 ms 348 KB Partially correct
58 Partially correct 0 ms 348 KB Partially correct
59 Partially correct 0 ms 348 KB Partially correct
60 Partially correct 1 ms 348 KB Partially correct
61 Partially correct 0 ms 348 KB Partially correct
62 Partially correct 356 ms 32268 KB Partially correct
63 Partially correct 355 ms 32200 KB Partially correct
64 Partially correct 383 ms 31864 KB Partially correct
65 Partially correct 414 ms 35128 KB Partially correct
66 Partially correct 464 ms 32172 KB Partially correct
67 Partially correct 470 ms 30588 KB Partially correct
68 Partially correct 277 ms 36888 KB Partially correct
69 Partially correct 0 ms 348 KB Partially correct
70 Partially correct 275 ms 38120 KB Partially correct
71 Partially correct 364 ms 32252 KB Partially correct
72 Partially correct 289 ms 32308 KB Partially correct
73 Partially correct 341 ms 33620 KB Partially correct
74 Partially correct 357 ms 31724 KB Partially correct
75 Partially correct 422 ms 31312 KB Partially correct
76 Partially correct 366 ms 32336 KB Partially correct
77 Partially correct 348 ms 30728 KB Partially correct
78 Partially correct 353 ms 39492 KB Partially correct
79 Partially correct 0 ms 348 KB Partially correct
80 Partially correct 0 ms 348 KB Partially correct
81 Partially correct 0 ms 348 KB Partially correct
82 Partially correct 1 ms 348 KB Partially correct
83 Partially correct 0 ms 348 KB Partially correct
84 Partially correct 1 ms 348 KB Partially correct
85 Partially correct 0 ms 348 KB Partially correct
86 Partially correct 1 ms 348 KB Partially correct
87 Partially correct 0 ms 348 KB Partially correct
88 Partially correct 0 ms 348 KB Partially correct
89 Partially correct 367 ms 32324 KB Partially correct
90 Partially correct 345 ms 32256 KB Partially correct
91 Partially correct 382 ms 31816 KB Partially correct
92 Partially correct 413 ms 35116 KB Partially correct
93 Partially correct 487 ms 32160 KB Partially correct
94 Partially correct 426 ms 30604 KB Partially correct
95 Partially correct 281 ms 36688 KB Partially correct
96 Partially correct 7 ms 1116 KB Partially correct
97 Partially correct 7 ms 1236 KB Partially correct
98 Partially correct 10 ms 1192 KB Partially correct
99 Partially correct 8 ms 1112 KB Partially correct
100 Partially correct 5 ms 1296 KB Partially correct
101 Partially correct 7 ms 1096 KB Partially correct
102 Partially correct 8 ms 1108 KB Partially correct
103 Partially correct 475 ms 34120 KB Partially correct
104 Partially correct 499 ms 38460 KB Partially correct
105 Partially correct 419 ms 37008 KB Partially correct
106 Partially correct 412 ms 38016 KB Partially correct
107 Partially correct 478 ms 31556 KB Partially correct
108 Partially correct 431 ms 31568 KB Partially correct
109 Partially correct 331 ms 32940 KB Partially correct
110 Partially correct 338 ms 31476 KB Partially correct
111 Partially correct 281 ms 32736 KB Partially correct
112 Partially correct 270 ms 33024 KB Partially correct