Submission #169890

#	Time	Username	Problem	Language	Result	Execution time	Memory
169890		Retro3014	Salesman (IOI09_salesman)	C++17	40 / 100	1087 ms	59592 KiB

salesman

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1000000000LL;
const int MAX_N = 500001;

int N;
ll U, D, S;
struct ST{
	ll t, l, m;
	bool operator <(const ST &a)const{
		if(t==a.t){
			return l<a.l;
		}
		return t<a.t;
	}
};
vector<ST> v;
struct SEG{
	struct NODE{
		int l, r;
		ll mx;
	};
	vector<NODE> seg;
	int SZ;
	void add(){seg.pb({-1, -1, -INFLL});}
	void Init(int x){
		add();
		SZ = x;
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e)	return;
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e);
	}
	void Update(int x, int y, ll z){
		update(0, 1, SZ, x, y, z);
	}
	void update(int idx, int s, int e, int x, int y, ll z){
		if(x<=s && e<=y)	{
			seg[idx].mx = max(seg[idx].mx, z);
			return;
		}
		if(x>e || y<s)	return;
		update(seg[idx].l, s, (s+e)/2, x, y, z); update(seg[idx].r, (s+e)/2+1, e, x, y, z);
	}
	ll Mx(int x){
		return mx(0, 1, SZ, x);
	}
	ll mx(int idx, int s, int e, int k){
		if(s==e)	return seg[idx].mx;
		if(k<=(s+e)/2){
			return max(seg[idx].mx, mx(seg[idx].l, s, (s+e)/2, k));
		}else{
			return max(seg[idx].mx, mx(seg[idx].r, (s+e)/2+1, e, k));
		}
	}
}Seg1, Seg2;

vector<pair<ll, int> > vt;

ll get(int idx){
	return max(Seg1.Mx(idx)+(ll)idx*U, Seg2.Mx(idx)-(ll)idx*D);
}
void Upd(int idx, ll x){
	Seg1.Update(1, idx, x-(ll)idx*U);
	Seg2.Update(idx, MAX_N, x+(ll)idx*D);
}

int main(){
	scanf("%d%lld%lld%lld", &N, &U, &D, &S);
	Seg1.Init(MAX_N); Seg2.Init(MAX_N);
	Upd(S, 0);
	for(int i=0; i<N; i++){
		ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
		v.pb({a, b, c});
	}
	sort(v.begin(), v.end());
	int s = 0, e = 0;
	while(s<v.size()){
		while(e+1<v.size() && v[e+1].t==v[s].t)	e++;
		for(int i=s; i<=e; i++){
			vt.pb({get(v[i].l), i});
		}
		sort(vt.begin(), vt.end());
		while(!vt.empty()){
			int n = vt.back().second;	vt.pop_back();
			Upd((int)v[n].l, get(v[n].l)+v[n].m);
		}
		s = e+1; e++;
	}
	cout<<get(S);
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:102:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(s<v.size()){
        ~^~~~~~~~~
salesman.cpp:103:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e+1<v.size() && v[e+1].t==v[s].t) e++;
         ~~~^~~~~~~~~
salesman.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld%lld", &N, &U, &D, &S);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:97:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 40 / 100