제출 #230003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230003		xiaowuc1	Salesman (IOI09_salesman)	C++14	100 / 100	944 ms	50860 KiB

salesman

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define derr if(1) cerr
typedef vector<int> vi;
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> matrix;
typedef pair<ll, ll> pll;

int downcost, upcost;
const int KOOSAGA_SZ = 1 << 19;
pll forupstream[2 * KOOSAGA_SZ];
pll upstreammerge(pll a, pll b) {
  if(a.first < b.first) swap(a, b);
  ll areal = a.second - (a.first - b.first) * upcost;
  if(areal >= b.second) return a;
  return b;
}
void upset(int idx, ll val) {
  forupstream[idx + KOOSAGA_SZ] = {idx, val};
  idx += KOOSAGA_SZ;
  while(idx > 1) {
    idx /= 2;
    forupstream[idx] = upstreammerge(forupstream[2*idx], forupstream[2*idx+1]);
  }
}
pll upqry(int lhs, int rhs) {
  pll ret = {0, -1e18};
  lhs += KOOSAGA_SZ;
  rhs += KOOSAGA_SZ;
  while(lhs <= rhs) {
    if(lhs == rhs) return upstreammerge(ret, forupstream[lhs]);
    if(lhs%2) ret = upstreammerge(ret, forupstream[lhs++]);
    if(rhs%2==0) ret = upstreammerge(ret, forupstream[rhs--]);
    lhs /= 2;
    rhs /= 2;
  }
  return ret;
}

pll fordownstream[2 * KOOSAGA_SZ];
pll downstreammerge(pll a, pll b) {
  if(a.first > b.first) swap(a, b);
  ll areal = a.second - (b.first - a.first) * downcost;
  if(areal >= b.second) return a;
  return b;
}
void downset(int idx, ll val) {
  fordownstream[idx + KOOSAGA_SZ] = {idx, val};
  idx += KOOSAGA_SZ;
  while(idx > 1) {
    idx /= 2;
    fordownstream[idx] = downstreammerge(fordownstream[2*idx], fordownstream[2*idx+1]);
  }
}
pll downqry(int lhs, int rhs) {
  pll ret = {0, -1e18};
  lhs += KOOSAGA_SZ;
  rhs += KOOSAGA_SZ;
  while(lhs <= rhs) {
    if(lhs == rhs) return downstreammerge(ret, fordownstream[lhs]);
    if(lhs%2) ret = downstreammerge(ret, fordownstream[lhs++]);
    if(rhs%2==0) ret = downstreammerge(ret, fordownstream[rhs--]);
    lhs /= 2;
    rhs /= 2;
  }
  return ret;
}

struct event {
  int t;
  int x;
  int gain;
  event(int a, int b, int c) {
    t=a;
    x=b;
    gain=c;
  }
  bool operator<(const event& e) {
    return t < e.t;
  }
};

bool locsort(event& a, event& b) {
  return a.x < b.x;
}

void solve() {
  vector<event> events;
  int n, start;
  cin >> n >> upcost >> downcost >> start;
  for(int i = 0; i < KOOSAGA_SZ; i++) {
    upset(i, -1e18);
    downset(i, -1e18);
  }
  upset(start, 0);
  downset(start, 0);
  for(int i = 0; i < n; i++) {
    int t, x, gain;
    cin >> t >> x >> gain;
    events.emplace_back(t, x, gain);
  }
  events.emplace_back(1000000, start, 0);
  sort(all(events));
  for(int i = 0; i < sz(events);) {
    int j = i+1;
    while(j < sz(events) && events[i].t == events[j].t) {
      j++;
    }
    vector<event> window;
    for(int k = i; k < j; k++) {
      window.push_back(events[k]);
    }
    sort(all(window), locsort);
    vector<ll> singlegain;
    for(int a = 0; a < sz(window); a++) {
      pll comedown = downqry(0, window[a].x - 1);
      pll comeup = upqry(window[a].x+1, KOOSAGA_SZ-1);
      singlegain.push_back(
        max(
          comedown.second - downcost * (window[a].x - comedown.first),
          comeup.second - upcost * (comeup.first - window[a].x)
        ) + window[a].gain
      );
      // derr << "single gain for event at " << window[a].x << " is tentatively " << singlegain.back() << endl;
    }
    vector<ll> downgain;
    for(int a = 0; a < sz(singlegain); a++) {
      downgain.push_back(singlegain[a]);
    }
    for(int a = 1; a < sz(singlegain); a++) {
      downgain[a] = max(downgain[a], downgain[a-1] - downcost * (window[a].x - window[a-1].x) + window[a].gain);
    }
    vector<ll> upgain;
    for(int a = 0; a < sz(singlegain); a++) {
      upgain.push_back(singlegain[a]);
    }
    for(int a = sz(singlegain)-2; a >= 0; a--) {
      upgain[a] = max(upgain[a], upgain[a+1] - upcost * (window[a+1].x - window[a].x) + window[a].gain);
    }
    for(int a = 0; a < sz(window); a++) {
      downset(window[a].x, max(downgain[a], upgain[a]));
      upset(window[a].x, max(downgain[a], upgain[a]));
    }
    i = j;
  }
  pll ret = downqry(start, start);
  cout << max(0LL, ret.second) << "\n";
}
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

• Subtask 1: 100 / 100