oj.uz

Submission #921497

# Submission time Handle Problem Language Result Execution time Memory
921497 2024-02-04T03:05:40 Z gs25 Salesman (IOI09_salesman) C++17
36 / 100
 3000 ms 56988 KB 
#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


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,-inf); 
	}
	
	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; 
}

int tmp1[MAXN],tmp2[MAXN]; 
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 seg1(MAXN), seg2(MAXN);
	 rep(i,N) sort(all(fuck[i]));
	 seg1.update(S,D*S);
	 seg2.update(S,-U*S);
	 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);
	 		tmp1[i] = bada(pos,M,seg1,seg2); 
	 		tmp2[i] = tmp1[i];
	 	}
	 	for(int i=1; i<t; i++){
	 		tmp1[i] = max(tmp1[i],vec[i].second + tmp1[i-1]-D*(vec[i].first - vec[i-1].first)); 
	 	}
	 	for(int i=t-2;i>=0;i--){
	 		tmp2[i] = max(tmp2[i],vec[i].second + tmp2[i+1]-U*(vec[i+1].first-vec[i].first));
	 	}
	 	for(int i=0; i<t; i++){
	 		auto& [pos,M] = vec[i];  
	 		dbg(tmp[i]);
	 		tmp1[i] = max(tmp1[i],tmp2[i]);
	 		seg1.update(pos,tmp1[i]+D*pos); 
	 		seg2.update(pos,tmp1[i]-U*pos); 
	 	}
	 	
	 	
	 	
	 }
	 cout << seg1.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

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

Subtask #1
36.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31576 KB Output is correct
2 Correct 10 ms 31580 KB Output is correct
3 Correct 29 ms 31688 KB Output is correct
4 Correct 87 ms 31860 KB Output is correct
5 Correct 255 ms 32336 KB Output is correct
6 Correct 835 ms 34708 KB Output is correct
7 Correct 2072 ms 39584 KB Output is correct
8 Execution timed out 3038 ms 44396 KB Time limit exceeded
9 Execution timed out 3052 ms 45632 KB Time limit exceeded
10 Execution timed out 3011 ms 50680 KB Time limit exceeded
11 Execution timed out 3038 ms 50440 KB Time limit exceeded
12 Execution timed out 3064 ms 53796 KB Time limit exceeded
13 Execution timed out 3020 ms 53604 KB Time limit exceeded
14 Execution timed out 3070 ms 56524 KB Time limit exceeded
15 Execution timed out 3050 ms 56988 KB Time limit exceeded
16 Execution timed out 3037 ms 56632 KB Time limit exceeded
17 Correct 10 ms 31576 KB Output is correct
18 Correct 21 ms 31580 KB Output is correct
19 Correct 49 ms 31716 KB Output is correct
20 Correct 107 ms 31908 KB Output is correct
21 Correct 108 ms 31824 KB Output is correct
22 Correct 210 ms 32224 KB Output is correct
23 Correct 208 ms 32340 KB Output is correct
24 Incorrect 205 ms 32084 KB Output isn't correct
25 Execution timed out 3036 ms 42848 KB Time limit exceeded
26 Execution timed out 3066 ms 43432 KB Time limit exceeded
27 Execution timed out 3040 ms 44720 KB Time limit exceeded
28 Execution timed out 3040 ms 45584 KB Time limit exceeded
29 Execution timed out 3016 ms 45916 KB Time limit exceeded
30 Execution timed out 3037 ms 46996 KB Time limit exceeded