Submission #44042

#	Time	Username	Problem	Language	Result	Execution time	Memory
44042		wxh010910	Construction of Highway (JOI18_construction)	C++17	100 / 100	294 ms	81272 KiB

construction

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 100005;

int n, top, c[N], d[N], f[N], siz[N], sta[N], val[N], chd[N][2];
vector <pii> seq;
LL ans, b[N];

inline bool IsRoot(int x) {
  return chd[f[x]][0] != x && chd[f[x]][1] != x;
}

inline void AddTag(int x, int y) {
  val[x] = c[x] = y;
}

inline void PushUp(int x) {
  siz[x] = siz[chd[x][0]] + siz[chd[x][1]] + 1;
}

inline void PushDown(int x) {
  if (val[x]) {
    AddTag(chd[x][0], val[x]), AddTag(chd[x][1], val[x]), val[x] = 0;
  }
}

inline void Rotate(int x) {
  int y = f[x], z = f[y], k = chd[y][1] == x;
  if (!IsRoot(y)) {
    chd[z][chd[z][1] == y] = x;
  }
  f[chd[y][k] = chd[x][!k]] = y;
  f[f[chd[x][!k] = y] = x] = z;
  PushUp(y), PushUp(x);
}

inline void Splay(int x) {
  sta[top = 1] = x;
  for (int i = x; !IsRoot(i); sta[++top] = i = f[i]);
  for (; top; PushDown(sta[top--]));
  for (int y = f[x], z = f[y]; !IsRoot(x); Rotate(x), y = f[x], z = f[y]) {
    if (!IsRoot(y)) {
      Rotate((chd[y][1] == x) == (chd[z][1] == y) ? y : x);
    }
  }
}

inline void Access(int x) {
  for (int t = 0; x; x = f[x]) {
    Splay(x), chd[x][1] = t, t = x, PushUp(x), seq.pb(mp(c[x], siz[x]));
  }
}

inline void Modify(int x, int y) {
  for (; x <= n; x += x & -x) {
    b[x] += y;
  }
}

inline LL Query(int x) {
  LL r = 0;
  for (; x; x -= x & -x) {
    r += b[x];
  }
  return r;
}

inline void Solve() {
  ans = 0;
  for (int i = seq.size() - 1; i; --i) {
    seq[i].Y -= seq[i - 1].Y;
  }
  for (int i = 0; i < seq.size(); ++i) {
    ans += 1LL * seq[i].Y * Query(seq[i].X - 1);
    Modify(seq[i].X, seq[i].Y);
  }
  printf("%lld\n", ans);
  for (int i = 0; i < seq.size(); ++i) {
    Modify(seq[i].X, -seq[i].Y);
  }
  seq.clear();
}

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n);
  for (int i = 1; i <= n; ++i) {
    Read(c[i]), d[i] = c[i], siz[i] = 1;
  }
  sort(d + 1, d + n + 1);
  for (int i = 1; i <= n; ++i) {
    c[i] = lower_bound(d + 1, d + n + 1, c[i]) - d;
  }
  for (int i = 1, x, y; i < n; ++i) {
    Read(x), Read(y);
    Access(x), Splay(x);
    AddTag(x, c[y]), f[y] = x, Solve();
  }
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void Solve()':
construction.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seq.size(); ++i) {
                   ~~^~~~~~~~~~~~
construction.cpp:116:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seq.size(); ++i) {
                   ~~^~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84