Submission #138464

#	Time	Username	Problem	Language	Result	Execution time	Memory
138464		baluteshih	Salesman (IOI09_salesman)	C++14	30 / 100	1085 ms	65536 KiB

salesman

#pragma GCC optimize("O3","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ET cout << "\n"
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define MEM memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct mode
{
	int ti,pl,earn;
	bool operator<(const mode &a)const{
		if(ti==a.ti) return pl<a.pl;
		return ti<a.ti;
	}
}arr[500005];

const int INF=2e9,MAXC=500001;
int dp[500005],u,d;

struct node
{
	int ansu,ansd,dpu,dpd,L,R,lazy,lazy2;
	node operator+(const node &a)const{
		return node{max({-INF,ansu,a.ansu,a.dpu+L}),max({-INF,ansd,a.ansd,dpd+a.R}),max(dpu,a.dpu),max(dpd,a.dpd),max(L,a.L),max(R,a.R),0,0};
	}
	node operator+(const int &a)const{
		return node{ansu,ansd+a,dpu,dpd,L,R+a,lazy+a,lazy2};
	}
	node operator-(const int &a)const{
		return node{ansu-a,ansd,dpu,dpd,L-a,R,lazy,lazy2-a};
	}
}seg[1548576];

void down(int rt)
{
	if(!seg[rt].lazy&&!seg[rt].lazy2) return;
	seg[rt<<1]=seg[rt<<1]+seg[rt].lazy,seg[rt<<1|1]=seg[rt<<1|1]+seg[rt].lazy;
	seg[rt<<1]=seg[rt<<1]-seg[rt].lazy2,seg[rt<<1|1]=seg[rt<<1|1]-seg[rt].lazy2;
	seg[rt].lazy=seg[rt].lazy2=0;
}

void build(int l,int r,int rt)
{
	if(l==r) 
		return seg[rt]=node{dp[l]-l*u+l*u+l*d,dp[l]+l*d-r*u-r*d,dp[l]-l*u,dp[l]+l*d,l*u+l*d,-r*u-r*d,0,0},void();
	int m=l+r>>1;
	build(l,m,rt<<1),build(m+1,r,rt<<1|1);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

void modify(int x,int l,int r,int rt)
{
	if(l!=r) down(rt);
	if(l==r)
		return seg[rt].ansu=dp[l]-l*u+l*u+l*d,seg[rt].ansd=dp[l]+l*d-r*u-r*d,seg[rt].dpu=dp[l]-l*u,seg[rt].dpd=dp[l]+l*d,void();
	int m=l+r>>1;
	if(x<=m) modify(x,l,m,rt<<1);
	else modify(x,m+1,r,rt<<1|1);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

void modify2(int x,int l,int r,int rt,int v)
{
	if(l!=r) down(rt);
	if(x<=l)
		return seg[rt]=seg[rt]+v,void();
	int m=l+r>>1;
	if(x<=m) modify2(x,l,m,rt<<1,v);
	modify2(x,m+1,r,rt<<1|1,v);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

void modify3(int x,int l,int r,int rt,int v)
{
	if(l!=r) down(rt);
	if(x<=l)
		return seg[rt]=seg[rt]-v,void();
	int m=l+r>>1;
	if(x<=m) modify3(x,l,m,rt<<1,v);
	modify3(x,m+1,r,rt<<1|1,v);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

node query(int L,int R,int l,int r,int rt)
{
	if(l!=r) down(rt);
	if(L<=l&&R>=r)
		return seg[rt];
	int m=l+r>>1;
	if(R<=m) return query(L,R,l,m,rt<<1);
	if(L>m) return query(L,R,m+1,r,rt<<1|1);
	return query(L,R,l,m,rt<<1)+query(L,R,m+1,r,rt<<1|1);
}

int main()
{jizz
	int n,ans=0;
	cin >> n >> u >> d >> arr[0].pl;
	for(int i=1;i<=n;++i)
		cin >> arr[i].ti >> arr[i].pl >> arr[i].earn;
	sort(arr+1,arr+n+1),fill(dp,dp+MAXC+1,-INF),dp[arr[0].pl]=0,build(1,MAXC,1);
	for(int i=1,j=1;i<=n;)
	{
		while(j<=n&&arr[i].ti==arr[j].ti)
			modify2(arr[j].pl,1,MAXC,1,arr[j].earn),modify3(arr[j].pl+1,1,MAXC,1,arr[j].earn),++j;
		for(int k=i;k<j;++k)
		{
			auto a=query(1,arr[k].pl,1,MAXC,1),b=query(arr[k].pl,MAXC,1,MAXC,1);
			dp[arr[k].pl]=max({dp[arr[k].pl],a.ansu+b.R+arr[k].pl*u,b.ansd+a.L-arr[k].pl*d});
		}
		for(;i<j;++i)
			modify2(arr[i].pl,1,MAXC,1,-arr[i].earn),modify3(arr[i].pl+1,1,MAXC,1,-arr[i].earn),modify(arr[i].pl,1,MAXC,1);
	}
	for(int i=1;i<=arr[0].pl;++i)
		ans=max(ans,dp[i]-(arr[0].pl-i)*d);
	for(int i=arr[0].pl+1;i<=MAXC;++i)
		ans=max(ans,dp[i]-(i-arr[0].pl)*u);
	cout << ans << "\n";
}

Compilation message (stderr)

salesman.cpp: In function 'void build(int, int, int)':
salesman.cpp:55:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'void modify(int, int, int, int)':
salesman.cpp:65:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'void modify2(int, int, int, int, int)':
salesman.cpp:76:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'void modify3(int, int, int, int, int)':
salesman.cpp:87:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'node query(int, int, int, int, int)':
salesman.cpp:98:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

• Subtask 1: 30 / 100