Submission #1233395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233395		Tenis0206	Tricks of the Trade (CEOI23_trade)	C++20	55 / 100	8105 ms	386876 KiB

trade

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int oo = LLONG_MAX;
const int nmax = 3e5;
const int vmax = 1e9;

int n, k;
int c[nmax + 5], s[nmax + 5];

int r[nmax + 5], poz[nmax + 5];
int poz_dr[nmax + 5];

int sum[nmax + 5];

bool ok[nmax + 5];

struct Node
{
    Node *st, *dr;
    int val, sum;
    Node()
    {
        st = dr = nullptr;
        val = sum = 0;
    }
    Node(int new_val, int new_sum)
    {
        st = dr = nullptr;
        this -> val = new_val;
        this -> sum = new_sum;
    }
    Node(Node *nod, int new_val, int new_sum)
    {
        this -> st = nod -> st;
        this -> dr = nod -> dr;
        this -> val = nod -> val + new_val;
        this -> sum = nod -> sum + new_sum;
    }
    Node(Node *son_st, Node *son_dr)
    {
        this -> st = son_st;
        this -> dr = son_dr;
        this -> val = this -> sum = 0;
        if(son_st != nullptr)
        {
            this -> val += son_st -> val;
            this -> sum += son_st -> sum;
        }
        if(son_dr != nullptr)
        {
            this -> val += son_dr -> val;
            this -> sum += son_dr -> sum;
        }
    }
};

Node *rt[nmax + 5];

Node *update(Node *nod, int poz, int val, int a, int b)
{
    if(a == b)
    {
        if(nod == nullptr)
        {
            return new Node(val, val * a);
        }
        return new Node(nod, val, val * a);
    }
    int mij = (a + b) >> 1;
    if(poz <= mij)
    {
        if(nod == nullptr)
        {
            return new Node(update(nullptr, poz, val, a, mij), nullptr);
        }
        return new Node(update(nod -> st, poz, val, a, mij), nod -> dr);
    }
    if(nod == nullptr)
    {
        return new Node(nullptr, update(nullptr, poz, val, mij + 1, b));
    }
    return new Node(nod -> st, update(nod -> dr, poz, val, mij + 1, b));
}

pair<int,int> caut(Node *nod_st, Node *nod_dr, int k, int a, int b)
{
    if(a == b)
    {
        return {a * k, a};
    }
    int mij = (a + b) >> 1;
    int cnt_dr = 0;
    if(nod_dr -> dr != nullptr)
    {
        cnt_dr += nod_dr -> dr -> val;
    }
    if(nod_st != nullptr && nod_st -> dr != nullptr)
    {
        cnt_dr -= nod_st -> dr -> val;
    }
    if(cnt_dr >= k)
    {
        if(nod_st == nullptr)
        {
            return caut(nullptr, nod_dr -> dr, k, mij + 1, b);
        }
        return caut(nod_st -> dr, nod_dr -> dr, k, mij + 1, b);
    }
    pair<int,int> aux = {0, 0};
    if(nod_st == nullptr)
    {
        aux = caut(nullptr, nod_dr -> st, k - cnt_dr, a, mij);
    }
    else
    {
        aux = caut(nod_st -> st, nod_dr -> st, k - cnt_dr, a, mij);
    }
    if(nod_dr -> dr != nullptr)
    {
        aux.first += nod_dr -> dr -> sum;
    }
    if(nod_st != nullptr && nod_st -> dr != nullptr)
    {
        aux.first -= nod_st -> dr -> sum;
    }
    return aux;
}

int get_sum(int st, int dr)
{
    return sum[dr] - sum[st - 1];
}

int cost(int st, int dr)
{
    int rez = -get_sum(st, dr);
    rez += caut(rt[st - 1], rt[dr], k, 1, vmax).first;
    return rez;
}

void divide(int st, int dr, int min_chosen, int max_chosen)
{
    if(st > dr)
    {
        return;
    }
    int mij = (st + dr) >> 1;
    r[mij] = -oo;
    poz[mij] = 0;
    for(int j=max(min_chosen, mij + k - 1);j<=max_chosen;j++)
    {
        if(cost(mij, j) > r[mij])
        {
            poz[mij] = j;
            r[mij] = cost(mij, j);
        }
    }
    divide(st, mij - 1, min_chosen, poz[mij]);
    divide(mij + 1, dr, poz[mij], max_chosen);
}

void divide_dr(int st, int dr, int min_chosen, int max_chosen)
{
    if(st > dr)
    {
        return;
    }
    int mij = (st + dr) >> 1;
    poz_dr[mij] = 0;
    for(int j=max(min_chosen, mij + k - 1);j<=max_chosen;j++)
    {
        if(cost(mij, j) == r[mij])
        {
            poz_dr[mij] = j;
        }
    }
    divide_dr(st, mij - 1, min_chosen, poz_dr[mij]);
    divide_dr(mij + 1, dr, poz_dr[mij], max_chosen);
}

pair<int,int> ai[4 * nmax + 5];

pair<int,int> Merge(pair<int,int> a, pair<int,int> b)
{
    if(a > b)
    {
        return a;
    }
    return b;
}

void update_poz(int poz, int val, int nod, int a, int b)
{
    if(a == b)
    {
        ai[nod].first = val;
        ai[nod].second = a;
        return;
    }
    int mij = (a + b) >> 1;
    if(poz <= mij)
    {
        update_poz(poz, val, nod * 2, a, mij);
    }
    else
    {
        update_poz(poz, val, nod * 2 + 1, mij + 1, b);
    }
    ai[nod] = Merge(ai[nod * 2], ai[nod * 2 + 1]);
}

pair<int,int> query(int qa, int qb, int nod, int a, int b)
{
    if(qa <= a && qb >= b)
    {
        return ai[nod];
    }
    int mij = (a + b) >> 1;
    if(qa <= mij && qb > mij)
    {
        return Merge(query(qa, qb, nod * 2, a, mij), query(qa, qb, nod * 2 + 1, mij + 1, b));
    }
    if(qa <= mij)
    {
        return query(qa, qb, nod * 2, a, mij);
    }
    return query(qa, qb, nod * 2 + 1, mij + 1, b);
}

void reduct(int st, int dr)
{
    int val = caut(rt[st - 1], rt[dr], k, 1, vmax).second;
    pair<int,int> rem = query(st, dr, 1, 1, n);
    while(rem.first >= val)
    {
        ok[rem.second] = true;
        update_poz(rem.second, 0, 1, 1, n);
        rem = query(st, dr, 1, 1, n);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        sum[i] = sum[i - 1] + c[i];
    }
    rt[0] = new Node();
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        update_poz(i, s[i], 1, 1, n);
        rt[i] = update(rt[i - 1], s[i], +1, 1, vmax);
    }
    divide(1, n - k + 1, k, n);
    divide_dr(1, n - k + 1, k, n);
    int rez = -oo;
    for(int i=1;i+k-1<=n;i++)
    {
        rez = max(rez, r[i]);
    }
    cout<<rez<<'\n';
    for(int i=1;i+k-1<=n;i++)
    {
        if(r[i] != rez)
        {
            continue;
        }
        for(int j=poz[i];j<=poz_dr[i];j++)
        {
            if(cost(i, j) != r[i])
            {
                continue;
            }
            reduct(i, j);
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ok[i];
    }
    cout<<'\n';
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 0 / 45