oj.uz

Submission #1007536

# Submission time Handle Problem Language Result Execution time Memory
1007536 2024-06-25T06:48:02 Z huutuan Salesman (IOI09_salesman) C++14
42 / 100
 409 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=5e5+10;
const int inf=2e9;

struct Node{
   int val;
   Node (int _val=-inf){
      val=_val;
   }
   Node operator+(const Node &b){
      return Node(max(val, b.val));
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void update(int k, int l, int r, int pos, int val){
      if (l==r){
         t[k].val=val;
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid) update(k<<1, l, mid, pos, val);
      else update(k<<1|1, mid+1, r, pos, val);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   Node get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return t[0];
      if (L<=l && r<=R) return t[k];
      int mid=(l+r)>>1;
      return get(k<<1, l, mid, L, R)+get(k<<1|1, mid+1, r, L, R);
   }
} st1, st2;

int n, s, f[N], f1[N], f2[N], val[N], tt[N];
int u, d;
set<int> st;
vector<int> v[N];

void calc(int t){
   sort(v[t].begin(), v[t].end());
   for (auto &i:v[t]){
      f1[i]=st1.get(1, 1, st1.n, 1, i).val-d*i;
      f2[i]=st2.get(1, 1, st2.n, i, st2.n).val+u*i;
   }
   vector<int> &vv=v[t];
   f2[vv[0]]+=val[vv[0]];
   f1[vv.back()]+=val[vv.back()];
   for (int i=1; i<(int)vv.size(); ++i) f2[vv[i]]=max(f2[vv[i]], f2[vv[i-1]]-d*(vv[i]-vv[i-1]))+val[vv[i]];
   for (int i=(int)vv.size()-2; i>=0; --i) f1[vv[i]]=max(f1[vv[i]], f1[vv[i+1]]-u*(vv[i+1]-vv[i]))+val[vv[i]];
   for (int i:vv){
      f[i]=max(f1[i], f2[i]);
      st1.update(1, 1, st1.n, i, f[i]+d*i);
      st2.update(1, 1, st2.n, i, f[i]-u*i);
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> u >> d >> s;
   for (int i=1; i<=n; ++i){
      int t, l, m; cin >> t >> l >> m;
      v[t].push_back(l);
      tt[l]=t;
      val[l]=m;
      st.insert(t);
   }
   st1.init(N); st2.init(N);
   st.insert(0);
   for (int i=0; i<N; ++i) f[i]=-inf;
   f[s]=0;
   st1.update(1, 1, st1.n, s, f[s]+d*s);
   st2.update(1, 1, st2.n, s, f[s]-u*s);
   v[0].push_back(s);
   v[500001].push_back(s);
   st.insert(500001);
   for (auto it=next(st.begin()); it!=st.end(); ++it){
      calc(*it);
   }
   cout << f[s] << '\n';
   return 0;
}

Subtask #1
42.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37464 KB Output is correct
2 Correct 7 ms 37464 KB Output is correct
3 Correct 8 ms 37468 KB Output is correct
4 Correct 9 ms 37812 KB Output is correct
5 Correct 12 ms 37976 KB Output is correct
6 Correct 31 ms 39004 KB Output is correct
7 Correct 67 ms 42332 KB Output is correct
8 Correct 170 ms 47172 KB Output is correct
9 Correct 187 ms 51628 KB Output is correct
10 Correct 340 ms 65536 KB Output is correct
11 Correct 409 ms 65536 KB Output is correct
12 Runtime error 281 ms 65536 KB Execution killed with signal 9
13 Runtime error 244 ms 65536 KB Execution killed with signal 9
14 Runtime error 368 ms 65536 KB Execution killed with signal 9
15 Runtime error 363 ms 65536 KB Execution killed with signal 9
16 Runtime error 348 ms 65536 KB Execution killed with signal 9
17 Correct 7 ms 37464 KB Output is correct
18 Incorrect 7 ms 37468 KB Output isn't correct
19 Incorrect 7 ms 37508 KB Output isn't correct
20 Incorrect 8 ms 37692 KB Output isn't correct
21 Incorrect 8 ms 37468 KB Output isn't correct
22 Incorrect 10 ms 37628 KB Output isn't correct
23 Incorrect 10 ms 37468 KB Output isn't correct
24 Incorrect 13 ms 37748 KB Output isn't correct
25 Incorrect 68 ms 37972 KB Output isn't correct
26 Incorrect 122 ms 41044 KB Output isn't correct
27 Incorrect 192 ms 43944 KB Output isn't correct
28 Incorrect 264 ms 46124 KB Output isn't correct
29 Incorrect 282 ms 46672 KB Output isn't correct
30 Incorrect 281 ms 47664 KB Output isn't correct