Submission #885740

#	Time	Username	Problem	Language	Result	Execution time	Memory
885740		vjudge1	Cake 3 (JOI19_cake3)	C++17	0 / 100	2 ms	2648 KiB

cake3

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)2e5 + 5;
const long long INF = (int)1e18;
const long long MOD = (int)1e9 + 7;

int n,m;
struct node{
	int v,c;
};
node a[MAX];
int s = 0;
ii st[MAX << 2];
vector<int> rt;
int siz = 0;
int res = 0;
int L = 1,R = 1;

ii operator + (const ii &a,const ii &b){
	return {a.X + b.X,a.Y + b.Y};
}
void update(int u,int val,int id = 1,int l = 1,int r = siz){
	if(l == r){
		
		//cout << u << " " << val << " : ";
		//cout << st[id].X << "," << st[id].Y << " ";
	
		st[id].X += val;
		st[id].Y += val * rt[l - 1];
		
		//cout << st[id].X << "," << st[id].Y << "\n";
		
		return;
	}
	int m = l + r >> 1;
	if(u <= m)update(u,val,id << 1,l,m);
	else update(u,val,id << 1 | 1,m + 1,r);
	st[id] = st[id << 1] + st[id << 1 | 1];
}
bool ok = 0;
int get(int val,int id = 1,int l = 1,int r = siz){
	//if(ok)cout << val << " " << id << " " << l << " " << r << " " << st[id].X << " " << st[id].Y << '\n';
 	if(val == 0)return 0;
	if(st[id].X <= val)return st[id].Y;
	if(l == r){
		int sum = st[id].Y;
		if(st[id].X > val)sum -= (st[id].X - val) * rt[l - 1];
		return sum;
	}
	int m = l + r >> 1;
	if(st[id << 1 | 1].X > val)return get(val,id << 1 | 1,m + 1,r);
	return st[id << 1 | 1].Y + get(val - st[id << 1 | 1].X,id << 1,l,m);
}
void add(int id){
	update(a[id].v,1);
}
void del(int id){
	update(a[id].v,-1);
}
int cost(int l,int r){
	while(L > l)add(--L);
	while(R < r)add(++R);
	while(L < l)del(L++);
	while(R > r)del(R--);
	//if(ok)cout << l << " " << r << " : \n";
	return get(m);
}
void solve(int l,int r,int u,int v){
	
	
	//cout << l << " " << r << " " << u << " " << v << '\n';
	if(l > r)return;
	int mid = l + r >> 1;
	
	ii best = {-INF,-1};
	for(int i = max(u,mid);i <= v;i++){
		int cnt = (a[i].c - a[mid].c) * 2;
		if(i - mid + 1 < m)continue;
		if(mid == 2 && i == 4)ok = 1;
		best = max(best,{cost(mid,i) - cnt,i});
		ok = 0;
	}
	

	//cout << "---- " << mid << " " << best.X << " " << best.Y << " " << v << "\n";
	if(best.Y == -1){
		solve(l,mid - 1,u,v);
		return;
	}
	res = max(res,best.X);
	solve(l,mid - 1,u,best.Y);
	solve(mid + 1,r,best.Y,v);
}
signed main(){
	
	read();
	
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> a[i].v >> a[i].c;
		rt.push_back(a[i].v);
	}
	
	sort(rt.begin(),rt.end());
	rt.erase(unique(rt.begin(),rt.end()),rt.end());
	siz = rt.size();
	
	
	sort(a + 1,a + 1 + n,[&](const node &a,const node &b){
		return a.c < b.c;
	});
	
	
	for(int i = 1;i <= n;i++){
		a[i].v = lower_bound(rt.begin(),rt.end(),a[i].v) - rt.begin() + 1;
	}
	//cout << "\n";

	add(1);
	solve(1,n,1,n);
	
	cout << res;
	
}

Compilation message (stderr)

cake3.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
cake3.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int m = l + r >> 1;
      |          ~~^~~
cake3.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
cake3.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |  int m = l + r >> 1;
      |          ~~^~~
cake3.cpp: In function 'void solve(long long int, long long int, long long int, long long int)':
cake3.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |  int mid = l + r >> 1;
      |            ~~^~~

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