Submission #128297

#	Time	Username	Problem	Language	Result	Execution time	Memory
128297		mahmoudbadawy	Cake 3 (JOI19_cake3)	C++17	0 / 100	12 ms	8952 KiB

cake3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define F first
#define S second

using namespace std;
using namespace __gnu_pbds;

typedef tree<
pair<int,int>,
null_type,
greater<pair<int,int> >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int N=100005;

pair<int,int> arr[N];
long long diff[N],sdiff[N];
ordered_set ss;
vector<int> upd[N];
int n,m;

struct nodes{
	long long val,lazy;
	nodes():val(0),lazy(0){}
	nodes(long long val):val(val),lazy(0){}
};

nodes operator +(const nodes &l,const nodes &r)
{
	nodes res;
	res.val=max(l.val,r.val);
	res.lazy=0;
	return res;
}

nodes btree[4*N];

void build(int node,int l,int r)
{
	if(l==r)
	{
		btree[node]=nodes(sdiff[l]);
		return;
	}
	int mid=(l+r)/2;
	build(node*2,l,mid);
	build(node*2+1,mid+1,r);
	btree[node]=btree[node*2]+btree[node*2+1];
}

void down(int node,int l,int r)
{
	if(btree[node].lazy)
	{
		btree[node].val+=btree[node].lazy;
		if(l!=r)
		{
			btree[node*2].lazy+=btree[node].lazy;
			btree[node*2+1].lazy+=btree[node].lazy;
		}
		btree[node].lazy=0;
	}
}

void update(int node,int l,int r,int ind,long long val)
{
	down(node,l,r);
	if(ind<l||ind>r) return;
	if(l==r)
	{
		btree[node]=nodes(btree[node].val+val);
		sdiff[l]+=val;
		return;
	}
	int mid=(l+r)/2;
	update(node*2,l,mid,ind,val);
	update(node*2+1,mid+1,r,ind,val);
	btree[node]=btree[node*2]+btree[node*2+1];
}

void update(int node,int l,int r,int ql,int qr,long long val)
{
	down(node,l,r);
	if(r<ql||qr<l) return;
	if(ql<=l&&r<=qr)
	{
		btree[node].lazy+=val;
		down(node,l,r);
		return;
	}
	int mid=(l+r)/2;
	update(node*2,l,mid,ql,qr,val);
	update(node*2+1,mid+1,r,ql,qr,val);
	btree[node]=btree[node*2]+btree[node*2+1];
}

nodes query(int node,int l,int r,int ql,int qr)
{
	down(node,l,r);
	if(r<ql||qr<l) return nodes();
	if(ql<=l&&r<=qr)
		return btree[node];
	int mid=(l+r)/2;
	return query(node*2,l,mid,ql,qr)+query(node*2+1,mid+1,r,ql,qr);
}

void update(int x,long long val)
{
	update(1,0,n-1,0,x,val);
}

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d",&arr[i].S,&arr[i].F);
		arr[i].F*=2;
	}
	sort(arr,arr+n);
	long long cur=0,las=0;
	// val = maxk(arr[i].S,arr[j].S) - arr[i].
	for(int i=n-1;i>=0;i--)
	{
		ss.insert({arr[i].S,i});
		if(ss.order_of_key({arr[i].S,i})<m)
		{
			cur+=arr[i].S;
			if(ss.size()>m)
				cur-=(*ss.find_by_order(m)).F;
		}
		else
		{
			upd[ss.order_of_key({arr[i].S,i})].push_back(i);
		}
		diff[i]=cur-las+arr[i].F-arr[i+1].F;
		sdiff[i]=diff[i]+sdiff[i+1];
		las=cur;
		//cout << cur << " " << arr[i].F << " " << arr[i+1].F << " " << diff[i] << endl;
	}
	build(1,0,n-1);
	int curp=m;
	long long ans=-(1LL<<60);
	for(int i=n-1;i>=m-1;i--)
	{
		//cout << query(1,0,n-1,i,i).val << " " << diff[i] << endl;
		ans=max(ans,query(1,0,n-1,0,i-m+1).val-arr[i].F);
		update(1,0,n-1,0,i-1,-arr[i].S);
		//update(1,0,n-1,0,i-1,-diff[i]);
		if(ss.order_of_key({arr[i].S,i})<m)
		{
			cur=0;
			for(int j:upd[curp])
			{
				update(1,0,n-1,0,j,arr[j].S-cur);
				cur=arr[j].S;
			}
			curp++;
		}
		ss.erase({arr[i].S,i});
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:130:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ss.order_of_key({arr[i].S,i})<m)
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
cake3.cpp:133:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ss.size()>m)
       ~~~~~~~~~^~
cake3.cpp:154:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ss.order_of_key({arr[i].S,i})<m)
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
cake3.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&arr[i].S,&arr[i].F);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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