| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 106548 |
2019-04-19T03:32:52 Z |
wilwxk |
Salesman (IOI09_salesman) |
C++11 |
|
1000 ms |
32380 KB |
#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
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
12 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
14 ms |
8704 KB |
Output is correct |
| 4 |
Correct |
20 ms |
8704 KB |
Output is correct |
| 5 |
Correct |
32 ms |
8832 KB |
Output is correct |
| 6 |
Correct |
97 ms |
17500 KB |
Output is correct |
| 7 |
Correct |
234 ms |
18552 KB |
Output is correct |
| 8 |
Correct |
461 ms |
20028 KB |
Output is correct |
| 9 |
Correct |
712 ms |
21604 KB |
Output is correct |
| 10 |
Execution timed out |
1071 ms |
26328 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1076 ms |
26796 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1052 ms |
28468 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1068 ms |
28792 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1063 ms |
32380 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1075 ms |
31832 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1063 ms |
31400 KB |
Time limit exceeded |
| 17 |
Correct |
13 ms |
8576 KB |
Output is correct |
| 18 |
Correct |
14 ms |
8576 KB |
Output is correct |
| 19 |
Correct |
18 ms |
8704 KB |
Output is correct |
| 20 |
Correct |
25 ms |
8704 KB |
Output is correct |
| 21 |
Correct |
21 ms |
8704 KB |
Output is correct |
| 22 |
Correct |
35 ms |
8832 KB |
Output is correct |
| 23 |
Correct |
35 ms |
8832 KB |
Output is correct |
| 24 |
Correct |
41 ms |
8832 KB |
Output is correct |
| 25 |
Correct |
834 ms |
19972 KB |
Output is correct |
| 26 |
Execution timed out |
1076 ms |
23116 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1073 ms |
26620 KB |
Time limit exceeded |
| 28 |
Execution timed out |
1066 ms |
26616 KB |
Time limit exceeded |
| 29 |
Execution timed out |
1063 ms |
29892 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1040 ms |
31268 KB |
Time limit exceeded |
