Submission #106548

#	Time	Username	Problem	Language	Result	Execution time	Memory
106548		wilwxk	Salesman (IOI09_salesman)	C++11	57 / 100	1076 ms	32380 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.

salesman

#include <bits/stdc++.h>
using namespace std;

struct cara {
	int x, val, id;
	bool operator<(cara outro) const {
		if(id==outro.id) return x<outro.x;
		return id<outro.id;
	}
};

const int MAXN=5e5+5;
const int INF=2e9+5;
cara v[MAXN];
vector<int> aux;
int seg[4*MAXN][2];
int lz[4*MAXN][2];
int dp[MAXN];
int n, xx, yy, ori;

void refresh(int sind, int ini, int fim, int k) {
	seg[sind][k]+=lz[sind][k];
	if(ini==fim) {
		lz[sind][k]=0; return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	lz[e][k]+=lz[sind][k]; lz[d][k]+=lz[sind][k];
	lz[sind][k]=0;
}

void update(int sind, int ini, int fim, int qini, int qfim, int val, int k, int k2) {
	refresh(sind, ini, fim, k);
	if(qfim<ini||qini>fim) return;
	if(qini<=ini&&qfim>=fim) {
		if(!k2) seg[sind][k]=val;
		else lz[sind][k]+=val, refresh(sind, ini, fim, k);
		return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	update(e, ini, m, qini, qfim, val, k, k2);
	update(d, m+1, fim, qini, qfim, val, k, k2);
	seg[sind][k]=max(seg[e][k], seg[d][k]);
}

int query(int sind, int ini, int fim, int qini, int qfim, int k) {
	refresh(sind, ini, fim, k);
	if(qfim<qini||qini>fim||qfim<ini) return -INF;
	if(qini<=ini&&qfim>=fim) return seg[sind][k];
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	return max( query(e, ini, m, qini, qfim, k), query(d, m+1, fim, qini, qfim, k) );
}

void build(int sind, int ini, int fim) {
	if(ini==fim) {
		seg[sind][0]=-INF;
		seg[sind][1]=-INF;
		return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	build(e, ini, m); build(d, m+1, fim);
	seg[sind][0]=seg[e][0];
	seg[sind][1]=seg[e][1];
}

void solve() {

	for(auto cur : aux) {
			int aa=query(1, 1, MAXN-2, 1, v[cur].x-1, 0);
			int bb=query(1, 1, MAXN-2, v[cur].x+1, MAXN-2, 1);
			dp[cur]=max(aa-v[cur].x*yy, bb+v[cur].x*xx);
	}
	for(auto cur : aux) {
		update(1, 1, MAXN-2, v[cur].x, v[cur].x, dp[cur]+v[cur].x*yy, 0, 0);
		update(1, 1, MAXN-2, v[cur].x, v[cur].x, dp[cur]-v[cur].x*xx, 1, 0);
	}

	for(auto cur : aux) {
		if(cur==aux[0]) continue;
		update(1, 1, MAXN-2, v[cur].x, MAXN-2, v[cur].val, 1, 1);
	}

	for(int i=0; i<aux.size(); i++) {
			int cur=aux[i];
			int aa=query(1, 1, MAXN-2, 1, v[cur].x-1, 0);
			int bb=query(1, 1, MAXN-2, v[cur].x+1, MAXN-2, 1);

			dp[cur]=max(aa-v[cur].x*yy, bb+v[cur].x*xx);
			dp[cur]+=v[cur].val;

			if(i!=aux.size()-1) update(1, 1, MAXN-2, 1, v[cur].x, v[cur].val, 0, 1);
			if(i!=aux.size()-1) update(1, 1, MAXN-2, v[aux[i+1]].x, MAXN-2, -v[aux[i+1]].val, 1, 1);
	}

	for(auto cur : aux) {
		if(cur==aux.back()) continue;
		update(1, 1, MAXN-2, 1, v[cur].x, -v[cur].val, 0, 1);
	}

	for(auto cur : aux) {
		update(1, 1, MAXN-2, v[cur].x, v[cur].x, dp[cur]+v[cur].x*yy, 0, 0);
		update(1, 1, MAXN-2, v[cur].x, v[cur].x, dp[cur]-v[cur].x*xx, 1, 0);
	}
}

int main() {
	scanf("%d %d %d %d", &n, &xx, &yy, &ori);
	for(int i=1; i<=n; i++) scanf("%d %d %d", &v[i].id, &v[i].x, &v[i].val);
	sort(v+1, v+1+n); build(1, 1, MAXN-2);

	dp[0]=0;
	update(1, 1, MAXN-2, ori, ori, ori*yy, 0, 0);
	update(1, 1, MAXN-2, ori, ori, -ori*xx, 1, 0);

	for(int i=1; i<=n; i++) {
		int prox=i;
		while(prox<=n&&v[prox].id==v[i].id) aux.push_back(prox++);
		solve(); aux.clear();
		i=prox-1;
	}

	int aa=query(1, 1, MAXN-2, 1, ori-1, 0);
	int bb=query(1, 1, MAXN-2, ori+1, MAXN-2, 1);
	int respf=max(aa-ori*yy, bb+ori*xx); respf=max(respf, 0);
	printf("%d\n", respf);

}

Compilation message (stderr)

salesman.cpp: In function 'void refresh(int, int, int, int)':
salesman.cpp:26:6: warning: unused variable 'm' [-Wunused-variable]
  int m=(ini+fim)/2; int e=sind*2; int d=e+1;
      ^
salesman.cpp: In function 'void solve()':
salesman.cpp:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<aux.size(); i++) {
               ~^~~~~~~~~~~
salesman.cpp:90:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i!=aux.size()-1) update(1, 1, MAXN-2, 1, v[cur].x, v[cur].val, 0, 1);
       ~^~~~~~~~~~~~~~
salesman.cpp:91:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i!=aux.size()-1) update(1, 1, MAXN-2, v[aux[i+1]].x, MAXN-2, -v[aux[i+1]].val, 1, 1);
       ~^~~~~~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &n, &xx, &yy, &ori);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:107:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d %d %d", &v[i].id, &v[i].x, &v[i].val);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask 157 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...