Submission #1070311

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1070311	2024-08-22T13:05:03 Z	GrindMachine	Tricks of the Trade (CEOI23_trade)	C++17	50 / 100	2544 ms	648632 KB

trade

#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:
edi

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct fenwick {
    int n;
    vector<T> tr;
    int LOG = 0;

    fenwick() {

    }

    fenwick(int n_) {
        n = n_;
        tr = vector<T>(n + 1);
        while((1<<LOG) <= n) LOG++;
    }

    void reset(){
        fill(all(tr),0);
    }

    int lsb(int x) {
        return x & -x;
    }

    void pupd(int i, T v) {
        for(; i <= n; i += lsb(i)){
            tr[i] += v;
        }
    }

    T sum(int i) {
        T res = 0;
        for(; i; i ^= lsb(i)){
            res += tr[i];
        }
        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }

    int lower_bound(T s){
        // first pos with sum >= s
        if(sum(n) < s) return n+1;
        int i = 0;
        rev(bit,LOG-1,0){
            int j = i+(1<<bit);
            if(j > n) conts;
            if(tr[j] < s){
                s -= tr[j];
                i = j;
            }
        }

        return i+1;
    }

    int upper_bound(T s){
        return lower_bound(s+1);
    }
};

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]; 
    vector<ll> p(n+5);
    rep1(i,n) p[i] = p[i-1]+a[i];

    multiset<ll> ms1,ms2;
    ll curr_sum = 0;
    ll lx = 1, rx = 0;

    auto transfer = [&](){
        while(!ms2.empty() and sz(ms1) < k){
            curr_sum += *ms2.rbegin();
            ms1.insert(*ms2.rbegin());
            ms2.erase(--ms2.end());
        }

        while(sz(ms1) > k){
            ll x = *ms1.begin();
            curr_sum -= x;
            ms1.erase(ms1.begin());
            ms2.insert(x);
        }

        if(ms2.empty()) return;

        while(true){
            ll mn1 = *ms1.begin(), mx2 = *ms2.rbegin();
            if(mn1 >= mx2) break;
            ms1.erase(ms1.find(mn1));
            ms2.erase(ms2.find(mx2));
            ms1.insert(mx2);
            ms2.insert(mn1);
            curr_sum += mx2-mn1;
        }
    };

    auto ins = [&](ll i){
        ms1.insert(b[i]);
        curr_sum += b[i];
        transfer();
    };

    auto del = [&](ll i){
        if(ms1.find(b[i]) != ms1.end()){
            ms1.erase(ms1.find(b[i]));
            curr_sum -= b[i];
        }
        else{
            ms2.erase(ms2.find(b[i]));
        }

        transfer();
    };

    auto f = [&](ll l, ll r){
        if(r-l+1 < k) return -inf2;
        
        // expand
        while(rx < r){
            rx++;
            ins(rx);
        }
        while(lx > l){
            lx--;
            ins(lx);
        }

        // contract
        while(rx > r){
            del(rx);
            rx--;
        }
        while(lx < l){
            del(lx);
            lx++;
        }

        ll sum = -(p[r]-p[l-1]);
        sum += curr_sum;
        return sum;
    };

    ll ans = -inf2;
    vector<pll> segs;

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

    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 i = optl; i <= optr; ++i){
            ll cost = f(mid,i);
            if(cost >= best){
                best = cost;
                optm = i;
            }
            upd(mid,i,cost);
        }

        go(l,mid-1,optl,optm,go);
        go(mid+1,r,optm,optr,go);
    };

    go(1,n-k+1,1,n,go);
    cout << ans << endl;

    vector<ll> c;
    rep1(i,n) c.pb(b[i]);
    c.pb(-1);
    sort(all(c));
    c.resize(unique(all(c))-c.begin());

    vector<ll> cb(n+5);
    rep1(i,n) cb[i] = lower_bound(all(c),b[i])-c.begin();

    vector<ll> pos[n+5];
    rep1(i,n) pos[cb[i]].pb(i);

    vector<array<ll,3>> here[n+5];
    ll siz = sz(segs);

    rep(i,siz){
        auto [l,r] = segs[i];
        here[(1+n)>>1].pb({l,r,i});
    }

    vector<ll> kth(siz);
    fenwick<ll> fenw(n+5);

    while(true){
        vector<array<ll,3>> nxt;
        fenw.reset();
        rev(mid,n,1){
            trav(i,pos[mid]){
                fenw.pupd(i,1);
            }

            for(auto [l,r,i] : here[mid]){
                ll cnt = fenw.query(l,r);
                if(cnt >= k){
                    kth[i] = mid;
                    nxt.pb({mid+1,r,i});
                }
                else{
                    nxt.pb({l,mid-1,i});
                }
            }
        }

        rep1(i,n) here[i].clear();
        
        bool ok = false;
        for(auto [l,r,i] : nxt){
            if(l > r) conts;
            ok = true;
            here[(l+r)>>1].pb({l,r,i});
        }

        if(!ok) break;
    }

    vector<ll> enter[n+5], leave[n+5];
    rep(i,siz){
        auto [l,r] = segs[i];
        enter[l].pb(kth[i]);
        leave[r+1].pb(kth[i]);
    }

    multiset<ll> ms;
    rep1(i,n){
        trav(x,enter[i]){
            ms.insert(x);
        }
        
        trav(x,leave[i]){
            ms.erase(ms.find(x));
        }

        if(!ms.empty() and cb[i] >= *ms.begin()){
            cout << 1;
        }
        else{
            cout << 0;
        }
    }

    cout << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #0

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct

Subtask #1

5.0 / 10.0

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

Subtask #2

5.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Partially correct	0 ms	348 KB	Partially correct
5	Correct	0 ms	348 KB	Output is correct
6	Partially correct	1 ms	348 KB	Partially correct
7	Partially correct	1 ms	348 KB	Partially correct
8	Correct	1 ms	360 KB	Output is correct
9	Partially correct	1 ms	348 KB	Partially correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Partially correct	0 ms	348 KB	Partially correct
16	Correct	0 ms	348 KB	Output is correct
17	Partially correct	1 ms	348 KB	Partially correct
18	Partially correct	1 ms	348 KB	Partially correct
19	Correct	1 ms	344 KB	Output is correct
20	Partially correct	1 ms	348 KB	Partially correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	3 ms	1628 KB	Output is correct
24	Partially correct	17 ms	1884 KB	Partially correct
25	Partially correct	28 ms	1912 KB	Partially correct
26	Partially correct	27 ms	1872 KB	Partially correct
27	Correct	27 ms	7764 KB	Output is correct
28	Partially correct	14 ms	1368 KB	Partially correct
29	Correct	18 ms	1628 KB	Output is correct

Subtask #3

5.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Partially correct	772 ms	55572 KB	Partially correct
3	Correct	1114 ms	42656 KB	Output is correct
4	Correct	1041 ms	45704 KB	Output is correct
5	Partially correct	1200 ms	74500 KB	Partially correct
6	Partially correct	1405 ms	76636 KB	Partially correct
7	Partially correct	2458 ms	64392 KB	Partially correct
8	Correct	1179 ms	42688 KB	Output is correct
9	Partially correct	1018 ms	42696 KB	Partially correct
10	Partially correct	1172 ms	55504 KB	Partially correct

Subtask #4

10.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Partially correct	772 ms	55572 KB	Partially correct
3	Correct	1114 ms	42656 KB	Output is correct
4	Correct	1041 ms	45704 KB	Output is correct
5	Partially correct	1200 ms	74500 KB	Partially correct
6	Partially correct	1405 ms	76636 KB	Partially correct
7	Partially correct	2458 ms	64392 KB	Partially correct
8	Correct	1179 ms	42688 KB	Output is correct
9	Partially correct	1018 ms	42696 KB	Partially correct
10	Partially correct	1172 ms	55504 KB	Partially correct
11	Correct	0 ms	344 KB	Output is correct
12	Partially correct	770 ms	55536 KB	Partially correct
13	Correct	1192 ms	42700 KB	Output is correct
14	Correct	1114 ms	45704 KB	Output is correct
15	Partially correct	1273 ms	74648 KB	Partially correct
16	Partially correct	1426 ms	76764 KB	Partially correct
17	Partially correct	2230 ms	64384 KB	Partially correct
18	Correct	1115 ms	42692 KB	Output is correct
19	Partially correct	1063 ms	42700 KB	Partially correct
20	Partially correct	1143 ms	55308 KB	Partially correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Partially correct	0 ms	348 KB	Partially correct
24	Correct	0 ms	348 KB	Output is correct
25	Partially correct	1 ms	348 KB	Partially correct
26	Partially correct	1 ms	348 KB	Partially correct
27	Correct	1 ms	348 KB	Output is correct
28	Partially correct	1 ms	348 KB	Partially correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	1496 ms	44488 KB	Output is correct
32	Partially correct	1156 ms	70404 KB	Partially correct
33	Partially correct	1791 ms	70872 KB	Partially correct
34	Partially correct	1851 ms	61260 KB	Partially correct
35	Partially correct	1837 ms	52660 KB	Partially correct
36	Partially correct	2474 ms	50640 KB	Partially correct
37	Correct	1333 ms	102720 KB	Output is correct

Subtask #5

25.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Partially correct	0 ms	348 KB	Partially correct
7	Correct	0 ms	348 KB	Output is correct
8	Partially correct	1 ms	348 KB	Partially correct
9	Partially correct	1 ms	348 KB	Partially correct
10	Correct	1 ms	360 KB	Output is correct
11	Partially correct	1 ms	348 KB	Partially correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Partially correct	0 ms	348 KB	Partially correct
18	Correct	0 ms	348 KB	Output is correct
19	Partially correct	1 ms	348 KB	Partially correct
20	Partially correct	1 ms	348 KB	Partially correct
21	Correct	1 ms	344 KB	Output is correct
22	Partially correct	1 ms	348 KB	Partially correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	3 ms	1628 KB	Output is correct
26	Partially correct	17 ms	1884 KB	Partially correct
27	Partially correct	28 ms	1912 KB	Partially correct
28	Partially correct	27 ms	1872 KB	Partially correct
29	Correct	27 ms	7764 KB	Output is correct
30	Partially correct	14 ms	1368 KB	Partially correct
31	Correct	18 ms	1628 KB	Output is correct
32	Correct	0 ms	344 KB	Output is correct
33	Partially correct	772 ms	55572 KB	Partially correct
34	Correct	1114 ms	42656 KB	Output is correct
35	Correct	1041 ms	45704 KB	Output is correct
36	Partially correct	1200 ms	74500 KB	Partially correct
37	Partially correct	1405 ms	76636 KB	Partially correct
38	Partially correct	2458 ms	64392 KB	Partially correct
39	Correct	1179 ms	42688 KB	Output is correct
40	Partially correct	1018 ms	42696 KB	Partially correct
41	Partially correct	1172 ms	55504 KB	Partially correct
42	Correct	0 ms	344 KB	Output is correct
43	Partially correct	770 ms	55536 KB	Partially correct
44	Correct	1192 ms	42700 KB	Output is correct
45	Correct	1114 ms	45704 KB	Output is correct
46	Partially correct	1273 ms	74648 KB	Partially correct
47	Partially correct	1426 ms	76764 KB	Partially correct
48	Partially correct	2230 ms	64384 KB	Partially correct
49	Correct	1115 ms	42692 KB	Output is correct
50	Partially correct	1063 ms	42700 KB	Partially correct
51	Partially correct	1143 ms	55308 KB	Partially correct
52	Correct	0 ms	344 KB	Output is correct
53	Correct	1 ms	348 KB	Output is correct
54	Partially correct	0 ms	348 KB	Partially correct
55	Correct	0 ms	348 KB	Output is correct
56	Partially correct	1 ms	348 KB	Partially correct
57	Partially correct	1 ms	348 KB	Partially correct
58	Correct	1 ms	348 KB	Output is correct
59	Partially correct	1 ms	348 KB	Partially correct
60	Correct	1 ms	348 KB	Output is correct
61	Correct	1 ms	348 KB	Output is correct
62	Correct	1496 ms	44488 KB	Output is correct
63	Partially correct	1156 ms	70404 KB	Partially correct
64	Partially correct	1791 ms	70872 KB	Partially correct
65	Partially correct	1851 ms	61260 KB	Partially correct
66	Partially correct	1837 ms	52660 KB	Partially correct
67	Partially correct	2474 ms	50640 KB	Partially correct
68	Correct	1333 ms	102720 KB	Output is correct
69	Correct	0 ms	348 KB	Output is correct
70	Partially correct	771 ms	55524 KB	Partially correct
71	Correct	1121 ms	42688 KB	Output is correct
72	Correct	1034 ms	45768 KB	Output is correct
73	Partially correct	1154 ms	74500 KB	Partially correct
74	Partially correct	1288 ms	76756 KB	Partially correct
75	Partially correct	2181 ms	64516 KB	Partially correct
76	Correct	1127 ms	42696 KB	Output is correct
77	Partially correct	990 ms	42700 KB	Partially correct
78	Partially correct	1173 ms	55432 KB	Partially correct
79	Correct	1 ms	344 KB	Output is correct
80	Correct	0 ms	348 KB	Output is correct
81	Partially correct	1 ms	348 KB	Partially correct
82	Correct	0 ms	348 KB	Output is correct
83	Partially correct	1 ms	344 KB	Partially correct
84	Partially correct	1 ms	344 KB	Partially correct
85	Correct	1 ms	348 KB	Output is correct
86	Partially correct	1 ms	348 KB	Partially correct
87	Correct	1 ms	348 KB	Output is correct
88	Correct	1 ms	348 KB	Output is correct
89	Correct	1493 ms	44744 KB	Output is correct
90	Partially correct	1140 ms	70364 KB	Partially correct
91	Partially correct	1825 ms	71448 KB	Partially correct
92	Partially correct	1936 ms	61524 KB	Partially correct
93	Partially correct	1901 ms	52808 KB	Partially correct
94	Partially correct	2511 ms	50516 KB	Partially correct
95	Correct	1290 ms	104740 KB	Output is correct
96	Correct	4 ms	1628 KB	Output is correct
97	Partially correct	17 ms	1884 KB	Partially correct
98	Partially correct	27 ms	1880 KB	Partially correct
99	Partially correct	26 ms	1916 KB	Partially correct
100	Correct	27 ms	7764 KB	Output is correct
101	Partially correct	14 ms	1368 KB	Partially correct
102	Correct	18 ms	1628 KB	Output is correct
103	Correct	2156 ms	53700 KB	Output is correct
104	Partially correct	2078 ms	49044 KB	Partially correct
105	Partially correct	2033 ms	58220 KB	Partially correct
106	Partially correct	2544 ms	63308 KB	Partially correct
107	Partially correct	382 ms	55496 KB	Partially correct
108	Partially correct	2365 ms	67992 KB	Partially correct
109	Correct	2484 ms	648632 KB	Output is correct
110	Partially correct	1722 ms	60444 KB	Partially correct
111	Correct	668 ms	52932 KB	Output is correct
112	Correct	2039 ms	259752 KB	Output is correct