Submission #921486

#	Time	Username	Problem	Language	Result	Execution time	Memory
921486		gs25	Salesman (IOI09_salesman)	C++17	0 / 100	161 ms	65536 KiB

salesman

#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, n) for (int i = 1; i <= n; ++i)
#define ff first
#define ss second
using namespace std;
typedef long long ll;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V> void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T> void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...)                                                              \
  cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = [";    \
  _print(x);                                                                   \
  cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define int ll 

int N,U,S,D; 
const int MAXN = 500010; 
vector<pair<int,int>> fuck[MAXN]; 

struct segment_tree{
	int n; vector<int> seg; 
	const int inf = 1e9; 
	segment_tree(int x){
		n = x+1; 
		seg.resize(4*n+8,0); 
	}
	
	void update(int node, int s, int e, int pos, int val){
		if(pos<s||pos>e) return; 
		if(s==e){
			seg[node] = val; return; 
		}
		int m = s+e>>1; 
		update(2*node,s,m,pos,val); 
		update(2*node+1,m+1,e,pos,val); 
		seg[node] = max(seg[2*node],seg[2*node+1]); 
		return; 
	}
	
	int query(int node, int s, int e, int l, int r){
		if(r<s||l>e) return -inf; 
		if(l<=s&&e<=r) return seg[node]; 
		int m = s+e>>1; 
		return max(query(2*node,s,m,l,r),query(2*node+1,m+1,e,l,r)); 
	}
	
	void update(int pos, int val){
		return update(1,0,n,pos,val); 
	}
	
	int query(int l, int r){
		return query(1,0,n,l,r); 
	}
}; 

const int inf = 1e9; 

int bada(int pos, int M, segment_tree& seg1, segment_tree& seg2){
	int lmax = M - D*pos + seg1.query(0,pos);
	int rmax = M + U*pos + seg2.query(pos,MAXN-1);
	dbg(lmax,rmax); 
	int MM = max(lmax,rmax); 
	seg1.update(pos,MM+D*pos); 
	seg2.update(pos,MM-U*pos); 
	return MM; 
}

void solve(){
	 cin >> N >> U >> D >> S; 
	 rep(i,N){
	 	int t,pos,M; cin >> t >> pos >> M; 
	 	fuck[t].pb({pos,M}); 
	 }
	 fuck[0].pb({S,0}); 
	 fuck[MAXN-1].pb({S,0}); 
	 segment_tree seg_up1(MAXN), seg_up2(MAXN), seg_down1(MAXN), seg_down2(MAXN); 
	 rep(i,N) sort(all(fuck[i]));
	 rep(i,MAXN){
	 	if(i==S){
	 		seg_up1.update(S,D*S);
	 		seg_up2.update(S,-U*S);
	 		seg_down1.update(S,D*S); 
	 		seg_down2.update(S,-U*S);
	 		continue;
	 	}
	 	seg_up1.update(i,-inf); 
	 	seg_up2.update(i,-inf); 
	 	seg_down1.update(i,-inf); 
	 	seg_down2.update(i,-inf); 
	 }
	 for(int i=1; i<MAXN; i++){
	 	if(fuck[i].size()==0) continue; 
	 	auto& vec = fuck[i]; 
	 	int t = vec.size();
	 	vector<int> tmp(t,0); 
	 	for(int i=0;i<t;i++){
	 		auto& [pos,M] = vec[i]; 
	 		dbg(pos,M);
	 		tmp[i] = bada(pos,M,seg_up1,seg_up2); 
	 	}
	 	for(int i=t-1;i>=0;i--){
	 		auto& [pos,M] = vec[i]; 
	 		tmp[i] = max(tmp[i],bada(pos,M,seg_down1,seg_down2)); 
	 	}
	 	for(int i=0; i<t; i++){
	 		auto& [pos,M] = vec[i];  
	 		dbg(tmp[i]);
	 		seg_up1.update(pos,tmp[i]+D*pos); 
	 		seg_up2.update(pos,tmp[i]-U*pos); 
	 		seg_down1.update(pos,tmp[i]+D*pos); 
	 		seg_down2.update(pos,tmp[i]-U*pos);
	 	}
	 }
	 cout << seg_up1.query(S,S) - D*S;
}

int32_t main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t=1; //cin >> t; 
    while(t--) solve(); 
}

Compilation message (stderr)

salesman.cpp: In member function 'void segment_tree::update(ll, ll, ll, ll, ll)':
salesman.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int m = s+e>>1;
      |           ~^~
salesman.cpp: In member function 'll segment_tree::query(ll, ll, ll, ll, ll)':
salesman.cpp:84:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |   int m = s+e>>1;
      |           ~^~

• Subtask 1: 0 / 100