제출 #1098626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098626		flyingkite	Cake 3 (JOI19_cake3)	C++17	100 / 100	1649 ms	26260 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
#define int long long
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll blocks = 350;
ll n,m, L = 0, R = 0;
pll a[N];
ll c[N], dp[N];
vector<pll>v;
struct segment_tree{
	ll n;
	vector<pair<ll,int>>st;
	void init(int _n){
		n = _n;
		st.resize(4 * n + 10);
	}
	pair<ll,int> merge(const pair<ll,int> &a, const pair<ll,int> &b){
		return {a.F + b.F, a.S + b.S};
	}
	void update(int id, int l, int r, int pos, ll val, int typ){
		if(l > pos || r < pos) return;
		if(l == r){
			st[id].F += val * typ;
			st[id].S += typ;
			return;
		}
		int mid = (l + r) / 2;
		update(2 * id, l, mid, pos, val, typ);
		update(2 * id + 1, mid + 1, r, pos, val, typ);
		st[id] = merge(st[2 * id], st[2 * id + 1]);
	}
	pair<ll,int> get(int id, int l, int r, int left, int right){
		if(l > right || r < left) return {0, 0};
		if(left <= l && r <= right) return st[id];
		int mid = (l + r) / 2;
		return merge(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
	}
	int walk(int id, int l, int r, int val){
		if(l == r) return l;
		int mid = (l + r) / 2;
		if(st[2 * id + 1].S > val) return walk(2 * id + 1, mid + 1, r, val);
		else if(st[id].S > val) return walk(2 * id, l, mid, val - st[2 * id + 1].S);
		else return -1;
	}
	pair<ll,int> get(int l, int r){return get(1,1,n,l,r);}
	void update(int pos, ll val, ll typ){update(1,1,n,pos,val,typ);}
} st;
void update(ll l, ll r){ // them tu 1 den r, xoa tu 1 den l - 1
	while(R < r){
		R++;
		st.update(c[R], a[R].F, 1);
	}
	while(R > r){
		st.update(c[R], a[R].F, -1);
		R--;
	}
	while(L < l - 1){
		L++;
		st.update(c[L], a[L].F, -1);
	}
	while(L > l - 1){
		st.update(c[L], a[L].F, 1);
		L--;
	}
}
void dnc(ll l, ll r, ll optl, ll optr){
	if(l > r) return;
	pll res = {-inf, -1};
	ll mid = (l + r) / 2;
 	for(int i = max(1ll, optl - 1); i <= min(mid - m + 1, optr);i++){
		update(i + 1, mid - 1);
		ll pos = st.walk(1,1,n,m-2);
		if(pos == -1) pos = 1;
		else pos++;
		ll x = st.get(pos, n).F;
		res = max(res, {x + a[i].F + a[mid].F - 2 * (a[mid].S - a[i].S), i});
	}
	dp[mid] = res.F;
	ll opt = res.S;
	dnc(l, mid - 1, optl, opt);
	dnc(mid + 1, r, opt, optr);
}
void to_thic_cau(){
	cin >> n >> m;
	for(int i = 1; i <= n;i++){
		cin >> a[i].F >> a[i].S;
	}
	sort(a + 1, a + n + 1, [&](const pll &a, const pll &b){
		return a.S < b.S;
	});
	for(int i = 1; i <= n;i++) v.pb({a[i].F, i});
	sort(all(v));
	for(int i = 0; i < v.size();i++) c[v[i].S] = i + 1;
	st.init(n);
	dnc(1,n,1,n);
	ll res = -inf;
	for(int i = 1; i <= n;i++) res = max(res, dp[i]);
	cout << res << "\n";
}
 
signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'void to_thic_cau()':
cake3.cpp:102:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 0; i < v.size();i++) c[v[i].S] = i + 1;
      |                 ~~^~~~~~~~~~

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