Submission #1179831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179831		justinlgl20	Cake 3 (JOI19_cake3)	C++20	100 / 100	885 ms	137728 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define all(x) (x).begin(), (x).end()
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {
    int f = 0; os << '{'; for (auto &i: x) os << (f++ ? ", " : ""), os << i; os << "}";
    return os;
}
 
void _print() {cerr << "]\n";}
 
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
 
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define pii pair<int, int>
#define f first
#define s second

vector<pii> val;
int root[2000005];
struct seg{
	struct node{
		int l,r,cnt,sum;
	} t[200005*30];
	int cnt=0;
	int make(int v,int l,int r,int n){// n is old node,v is index we are adding in
		if(r<v or v<l)return n;
		int cur=++cnt;
		t[cur]=t[n];
		if(l!=r){
			int mid=(l+r)>>1;
			t[cur].l=make(v,l,mid,t[n].l);
			t[cur].r=make(v,mid+1,r,t[n].r);
		}
		t[cur].cnt++;
		t[cur].sum+=val[v].f;
		return cur;
	}
	int query(int sum,int l,int r,int n1,int n2){
		if(l==r)return val[l].f*sum;
		int rcnt=t[t[n2].r].cnt-t[t[n1].r].cnt;
		int tot=t[t[n2].r].sum-t[t[n1].r].sum;
		int mid=(l+r)>>1;
		if(rcnt>sum)return query(sum,mid+1,r,t[n1].r,t[n2].r);
		else return tot+query(sum-rcnt,l,mid,t[n1].l,t[n2].l);
	}
} segtree;
int m,n,ans=-1e18;
vector<pii> a;
void solve(int s,int e,int l,int r){
	if(r<l)return;
	int mid=(l+r)>>1;
	int opt=e,best=-1e18;
	for(int i=max(s,mid+m-1);i<=e;i++){
		int val=segtree.query(m,1,n,root[mid-1],root[i])-2ll*(a[i].s-a[mid].s);
		if(val>=best){
			best=val;
			opt=i;
		}
	}
	ans=max(ans,best);
	solve(s,opt,l,mid-1);solve(opt,e,mid+1,r);
}

int32_t main() {
	cin>>n>>m;
	a.resize(n);
	for(int i=0;i<n;i++)cin>>a[i].f>>a[i].s;//val, minusthingy
	
	// inx in seg is coord compressed val
	sort(all(a));
	val=a;
	val.insert(val.begin(),make_pair(0,0));
	map<int,int> comp;
	for(int i=1;i<=n;i++){
		comp[val[i].f]=i;
	}
	sort(all(a),[&](pii a,pii b){
		if(a.s==b.s)return a.f<b.f;
		return a.s<b.s;
	});
	a.insert(a.begin(),make_pair(0,0));
	for(int i=1;i<=n;i++){
		root[i]=segtree.make(comp[a[i].f],1,n,root[i-1]);
	}
	solve(1,n,1,n);
	cout<<ans<<"\n";
}

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