Submission #572662

#	Time	Username	Problem	Language	Result	Execution time	Memory
572662		perchuts	Cake 3 (JOI19_cake3)	C++17	100 / 100	924 ms	186700 KiB

cake3

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const ll inf = 1e18;
const int mod = 1e9+7;
const int maxn = 2e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

ll custo[maxn], valor[maxn], best = -inf;
vector<int>ordc, ordv;

int n,m, pos[maxn];

//seg persistente é a unica solve que eu pensei...
//seg[i] guarda a raiz da seg pos eu conto as frequencias do prefixo ate i
//simplesmente fazer uma busca somando seg[md] e tirando seg[i] e pegar o (m-2)-ésimo maior elemento, depois
//somo todo mundo. nlog^2, mas tem constante mt fudida por causa da persistencia
//torcer pra passar no tl e no ml

struct Node{
    Node *l, *r;
    int freq;
    ll sum;
    Node(Node *l, Node *r,ll sum): l(l), r(r), freq(1), sum(sum){};
    Node(Node *l,Node *r): l(l), r(r), freq(l->freq+r->freq), sum(l->sum+r->sum){};
}*root[maxn], *null;


Node* update(Node *cur,int l,int r,int x){
    if(l==r)return new Node(null,null,valor[ordv[x]]);
    int md = (l+r)/2;
    if(x<=md)return new Node(update(cur->l,l,md,x),cur->r);
    return new Node(cur->l,update(cur->r,md+1,r,x));
}

ll busca(Node *cur1,Node *cur2,int l,int r,int x){
    if(l==r){
        assert(x<=1);
        return (x?cur1->sum-cur2->sum:0);
    }
    int md = (l+r)/2, qnt = cur1->r->freq - cur2->r->freq;
    if(x<=qnt)return busca(cur1->r,cur2->r,md+1,r,x);
    return busca(cur1->l,cur2->l,l,md,x-qnt)+cur1->r->sum-cur2->r->sum;
}

void compute(int l,int r,int lx,int rx){
    if(l>r)return;
    int md = (l+r)/2, opt=-1;
    ll melhor = -inf;
    for(int i=lx;i<=min(md,rx);++i){
        if(md-i-1<m-2)break;
        if(ckmax(melhor,valor[ordc[i]]+valor[ordc[md]]+busca(root[md-1],root[i],1,n,m-2) - 2*(custo[ordc[md]]-custo[ordc[i]])))opt = i;
    }
    ckmax(best,melhor);
    if(opt==-1)compute(l,md-1,lx,rx),compute(md+1,r,lx,rx);
    else compute(l,md-1,lx,opt), compute(md+1,r,opt,rx);
}

int main(){_
    cin>>n>>m;
    null = new Node(nullptr,nullptr,0), null->l = null->r = null, null->sum = null->freq = 0, root[0] = null;

    for(int i=1;i<=n;++i)cin>>valor[i]>>custo[i];
    
    ordc.resize(n+1), ordv.resize(n+1);
    iota(all(ordc),0), iota(all(ordv),0);

    sort(all(ordc),[&](int x,int y){return custo[x]<custo[y];});
    sort(all(ordv),[&](int x,int y){return valor[x]<valor[y];});

    for(int i=1;i<=n;++i)pos[ordv[i]] = i;  

    for(int i=1;i<=n;++i)root[i] = update(root[i-1],1,n,pos[ordc[i]]);
    
    compute(1,n,1,n);

    cout<<best<<endl;    
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76