Submission #47406

#	Time	Username	Problem	Language	Result	Execution time	Memory
47406		daniel_02	Construction of Highway (JOI18_construction)	C++17	7 / 100	1077 ms	1184 KiB

construction

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front

using namespace std;

const int N = 4000 + 7;
const int inf = 4000+7;

int a[N], pr[N];

struct con
{
    int l, r;
    ll sm;
    con()
    {

        l = r = sm = 0;
    }
}t[N * 4];
int cnt;

void update(int v, int tl, int tr, int pos, int x)
{
    if (tl == tr)
    {
        t[v].sm = max(t[v].sm + x, 0LL);
    }
    else
    {
        int mid = (tl + tr) >> 1;

        if (mid >= pos)
        {
            if (!t[v].l)
                t[v].l = ++cnt;

            update(t[v].l, tl, mid, pos, x);
        }
        else
        {
            if (!t[v].r)
                t[v].r = ++cnt;

            update(t[v].r, mid + 1, tr, pos, x);
        }
        if (!t[v].l)t[v].l = ++cnt;
        if (!t[v].r)t[v].r = ++cnt;

        t[v].sm = t[t[v].l].sm + t[t[v].r].sm;
    }
}
ll get(int v, int tl, int tr, int l, int r)
{
    if (tl > r || l > tr)return 0LL;

    if (l <= tl && tr <= r)
    {
        return t[v].sm;
    }
    else
    {
        int mid = (tl + tr) >> 1;

        if (!t[v].l)
            t[v].l = ++cnt;
        if (!t[v].r)
            t[v].r = ++cnt;

        return get(t[v].l, tl, mid, l, r) + get(t[v].r, mid + 1, tr, l, r);
    }
}
deque<int>dq;

void dfs(int v)
{
    while (v != 0) {
        dq.pf(a[v]);
        v = pr[v];
    }
}
void conquer(int v)
{
    ll ans = 0;
    dfs(v);

    cnt = 1;
    for (int i = 0; i < dq.size(); i++)
    {
        ans += get(1, 1, N, dq[i] + 1, N);
        update(1, 1, N, dq[i], 1);
    }
//    for (int i = 0; i < dq.size(); i++)
//        update(1, 1, inf, dq[i], -inf);
    memset(t, 0, sizeof(t));
    dq.clear();
    printf("%lld\n", ans);
}
void upd(int v, int x)
{
   while (v != 0) {
        a[v] = x;
        v = pr[v];
   }
}
vector <int> vec;

main()
{
    int n;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        vec.pb(a[i]);
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());

    for (int i = 1; i <= n; i ++) {
        a[i] = lower_bound(vec.begin(),vec.end(),a[i]) - vec.begin() + 1;
    }

    for (int i = 1; i < n; i++)
    {
        int q, w;
        scanf("%d%d", &q, &w);
        if (i == 1)
        {
            puts("0");
            pr[w] = q;
            a[q] = a[w];
            continue;
        }
        conquer(q);
        upd(q, a[w]);
        pr[w] = q;
    }
}

Compilation message (stderr)

construction.cpp: In function 'void conquer(int)':
construction.cpp:93:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < dq.size(); i++)
                     ~~^~~~~~~~~~~
construction.cpp: At global scope:
construction.cpp:113:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
construction.cpp: In function 'int main()':
construction.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
construction.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &q, &w);
         ~~~~~^~~~~~~~~~~~~~~~

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