Submission #47381

#	Time	Username	Problem	Language	Result	Execution time	Memory
47381		Talant	Construction of Highway (JOI18_construction)	C++17	16 / 100	271 ms	972 KiB

construction

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

const int inf = (int)1e9 + 7;
const int N = (int)4200;

int n;
int c[N];
int a,b;
int pr[N];
int t[N];

vector <int> vec;

void upd (int x) {
      for (; x < N; x += (x & -x))
            t[x] ++;
}
int get (int x) {
      int res = 0;
      for (; x > 0; x -= (x & -x)) {
            res += t[x];
      }
      return res;
}
main () {
      cin >> n;

      for (int i = 1; i <= n; i ++) {
            cin >> c[i];
            vec.pb(c[i]);
      }

      sort (all(vec));
      vec.erase (unique(all(vec)),vec.end());

      for (int i = 1; i <= n; i ++)
            c[i] = lower_bound(all(vec),c[i]) - vec.begin() + 2;

      int q = n - 1;

      pr[1] = -1;

      while (q --) {
            scanf ("%lld%lld", &a,&b);

            int ans = 0;

            pr[b] = a;

            deque <int> v;

            while (a != -1) {
                  v.push_front(a);
                  a = pr[a];
            }
            for (int i = v.size() - 1; i >= 0; i --) {
                  ans += get(c[v[i]] - 1);
                  upd(c[v[i]]);
            }

            for (int i = 0; i < v.size(); i ++)
                  c[v[i]] = c[b];

            printf("%lld\n", ans);
            memset(t,0,sizeof(t));
      }
}

Compilation message (stderr)

construction.cpp:35:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
construction.cpp: In function 'int main()':
construction.cpp:71:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < v.size(); i ++)
                             ~~^~~~~~~~~~
construction.cpp:54:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ("%lld%lld", &a,&b);
             ~~~~~~^~~~~~~~~~~~~~~~~~~

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