| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 138462 | baluteshih | Salesman (IOI09_salesman) | C++14 | 1087 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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=1e9,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[1048576];
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)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||