Submission #553871

#	Time	Username	Problem	Language	Result	Execution time	Memory
553871		MilosMilutinovic	Cake 3 (JOI19_cake3)	C++14	100 / 100	617 ms	82724 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=200050;
const int M=20*N;
int n,m,c[N],v[N],ord[N],vv[N];
int root[N],ls[M],rs[M],tsz,cc[M];
ll ans,st[M];
PII pp[N];

void modify(int p,int&c,int l,int r,int i,int v) {
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];st[c]=st[p]+v;cc[c]=cc[p]+1;
	if (l==r) return;
	int mid=(l+r)/2;
	if (i<=mid) modify(ls[p],ls[c],l,mid,i,v);
	else modify(rs[p],rs[c],mid+1,r,i,v);
}

ll query(int p,int c,int l,int r,int x) {
	if (!c) return 0ll;
	if (l==r) {return x>=1?st[c]-st[p]:0ll;}
	int mid=(l+r)/2;
	if (cc[rs[c]]-cc[rs[p]]<x) return st[rs[c]]-st[rs[p]]+query(ls[p],ls[c],l,mid,x-(cc[rs[c]]-cc[rs[p]]));
	else return query(rs[p],rs[c],mid+1,r,x);
}

void solve(int l,int r,int tl,int tr) {
	if (l>r) return;
	int mid=(l+r)/2;
	int opt=tl;
	ll mx=(ll)-1e18;
	rep(i,tl,min(tr+1,mid-m+2)) {
		ll cs=query(root[i-1],root[mid],1,n,m)-(c[mid]-c[i])*2;
		if (cs>mx) mx=cs,opt=i;
	}
	ans=max(ans,mx);
	solve(l,mid-1,tl,opt);
	solve(mid+1,r,opt,tr);
}

int main() {
	scanf("%d%d",&n,&m);
	rep(i,1,n+1) scanf("%d%d",v+i,c+i);
	rep(i,1,n+1) pp[i]=mp(c[i],v[i]);
	sort(pp+1,pp+1+n);
	rep(i,1,n+1) v[i]=pp[i].se,c[i]=pp[i].fi;
	rep(i,1,n+1) ord[i]=i;
	sort(ord+1,ord+1+n,[&](int i,int j){return v[i]<v[j];});
	rep(i,1,n+1) vv[ord[i]]=i;
	rep(i,1,n+1) {
		modify(root[i-1],root[i],1,n,vv[i],v[i]);
	}
	ans=-1e18;
	solve(1,n,1,n);
	printf("%lld",ans);
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
cake3.cpp:62:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  rep(i,1,n+1) scanf("%d%d",v+i,c+i);
      |               ~~~~~^~~~~~~~~~~~~~~~

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