Submission #62057

#	Time	Username	Problem	Language	Result	Execution time	Memory
62057		gusfring	Construction of Highway (JOI18_construction)	C++14	100 / 100	445 ms	51944 KiB

construction

#include <bits/stdc++.h>
 
using namespace std;
 
#define X first
#define Y second
#define mp make_pair
#define pb push_back
 
typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

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];
 
bool IsRoot(int x) {
  return chd[f[x]][0] != x && chd[f[x]][1] != x;
}
 
void AddTag(int x, int y) {
  val[x] = c[x] = y;
}
 
void PushUp(int x) {
  siz[x] = siz[chd[x][0]] + siz[chd[x][1]] + 1;
}
 
void PushDown(int x) {
  if (val[x]) {
    AddTag(chd[x][0], val[x]), AddTag(chd[x][1], val[x]), val[x] = 0;
  }
}
 
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);
}
 
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);
    }
  }
}
 
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]));
  }
}
 
void Modify(int x, int y) {
  for (; x <= n; x += x & -x) {
    b[x] += y;
  }
}
 
LL Query(int x) {
  LL r = 0;
  for (; x; x -= x & -x) {
    r += b[x];
  }
  return r;
}
 
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() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &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) {
    scanf("%d %d", &x, &y);
    Access(x), Splay(x);
    AddTag(x, c[y]), f[y] = x, Solve();
  }
  return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void Solve()':
construction.cpp:86:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seq.size(); ++i) {
                   ~~^~~~~~~~~~~~
construction.cpp:91:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seq.size(); ++i) {
                   ~~^~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
construction.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c[i]); d[i] = c[i], siz[i] = 1;
     ~~~~~^~~~~~~~~~~~~
construction.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~

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