Submission #61999

#	Time	Username	Problem	Language	Result	Execution time	Memory
61999		gusfring	Construction of Highway (JOI18_construction)	C++14	16 / 100	2028 ms	13820 KiB

construction

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, c[N], p[N], fen[N];
vector <int> vec;

void update(int pos, int val){
  for(; pos <= n; pos |= pos + 1) fen[pos] += val;
}

int get(int pos){
  int res = 0;
  for(; pos > 0; pos = (pos & (pos + 1)) - 1)
        res += fen[pos];
  return res;
}

int main(){
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++){
    scanf("%d", &c[i]);
    vec.emplace_back(c[i]);
  }
  sort(vec.begin(), vec.end());
  vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  for(int i = 1; i <= n; i ++){
    c[i] = lower_bound(vec.begin(), vec.end(), c[i]) - vec.begin() + 1;
  }
  for(int i = 1; i < n; i ++){
    int a, b;
    scanf("%d %d", &a, &b);
    int v = a, ans = 0;
    while(v){
      update(c[v], 1);
      ans += get(c[v] - 1);
      v = p[v];
    }
    v = a;
    while(v){
      update(c[v], -1);
      c[v] = c[b];
      v = p[v];
    }
    printf("%d\n", ans);
    p[b] = a;
  }
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
construction.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c[i]);
     ~~~~~^~~~~~~~~~~~~
construction.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~

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