이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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)return;
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |