oj.uz

Submission #379525

# Submission time Handle Problem Language Result Execution time Memory
379525 2021-03-18T12:14:11 Z N_o_o_B Tree Rotations (POI11_rot) C++14
63 / 100
 1000 ms 23404 KB 
#include <bits/stdc++.h>

namespace std
{

template <class Fun>
class y_combinator_result
{
    Fun fun_;

public:
    template <class T>
    explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

    template <class... Args>
    decltype(auto) operator()(Args &&... args)
    {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun)
{
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second

clock_t time_p = clock();
void time_taken()
{
    time_p = clock() - time_p;
    cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}

const ll mod = 1e9 + 7;
const ll INF = 1e18;

#include <bits/extc++.h>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// s.order_of_key(x) -> Number of elements in s strictly smaller than x
// auto it = s.find_by_order(k) -> iterator to the kth smallest element(0-indexed)

struct BIT
{
    vector<int> bit;
    BIT(int n = 1e5 + 6) : bit(n)
    {
    }
    void update(int x, int v)
    {
        while (x < int(bit.size()))
        {
            bit[x] += v;
            x += (x & -x);
        }
    }
    int query(int x)
    {
        int sum = 0;
        while (x > 0)
        {
            sum += bit[x];
            x -= (x & -x);
        }
        return sum;
    }
    void upd_range(int l, int r, int v)
    {
        update(l, v);
        update(r + 1, -v);
    }
    long long query_range(int l, int r)
    {
        return query(r) - query(l - 1);
    }
};

int main()
{
    // ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int n;
    scanf("%d", &n);

    array<int, 2> adj[2 * n + 10];

    vi sub(2 * n + 10), val(2 * n + 10);

    BIT b(n + 10);
    ll ans = 0;
    int cur = 0;

    function<int()> read = [&]() -> int {
        int p;
        scanf("%d", &p);
        int me = cur++;
        val[me] = p;
        sub[me] = 1;
        if (p)
        {
            return 1;
        }
        adj[me][0] = cur;
        sub[me] += read();
        adj[me][1] = cur;
        sub[me] += read();
        return sub[me];
    };
    read();

    function<vi(int, bool)> go = [&](int u, bool keep) -> vi {
        vi ret;
        if (val[u])
        {
            if (keep)
                b.update(val[u], 1);
            ret.pb(val[u]);
            return ret;
        }
        bool fl = (sub[adj[u][0]] > sub[adj[u][1]]);
        if (fl)
        {
            ll i1 = 0, i2 = 0;
            auto v1 = go(adj[u][1], false);
            auto v2 = go(adj[u][0], true);
            ret = v2;
            for (int x : v1)
            {
                ret.pb(x);
                int lt = b.query(x);
                int gt = sz(v2) - lt;
                i1 += lt;
                i2 += gt;
            }
            if (keep)
            {
                for (int x : v1)
                    b.update(x, 1);
            }
            else
            {
                for (int x : v2)
                    b.update(x, -1);
            }
            ans += min(i1, i2);
        }
        else
        {
            ll i1 = 0, i2 = 0;
            auto v1 = go(adj[u][0], false);
            auto v2 = go(adj[u][1], true);
            ret = v2;
            for (int x : v1)
            {
                ret.pb(x);
                int lt = b.query(x);
                int gt = sz(v2) - lt;
                i1 += lt;
                i2 += gt;
            }
            if (keep)
            {
                for (int x : v1)
                    b.update(x, 1);
            }
            else
            {
                for (int x : v2)
                    b.update(x, -1);
            }
            ans += min(i1, i2);
        }
        return ret;
    };
    go(0, 1);

    printf("%lld\n", ans);

    return 0;
}

Compilation message

rot.cpp: In function 'int main()':
rot.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
rot.cpp: In lambda function:
rot.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |         scanf("%d", &p);
      |         ~~~~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1132 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 6 ms 1132 KB Output is correct
4 Correct 7 ms 1260 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2924 KB Output is correct
2 Correct 10 ms 1132 KB Output is correct
3 Correct 23 ms 1900 KB Output is correct
4 Correct 20 ms 2284 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2864 KB Output is correct
2 Correct 141 ms 5996 KB Output is correct
3 Correct 252 ms 8580 KB Output is correct
4 Correct 284 ms 8896 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 17772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 7856 KB Output is correct
2 Execution timed out 1091 ms 11440 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 15340 KB Output is correct
2 Correct 530 ms 15036 KB Output is correct
3 Correct 317 ms 13956 KB Output is correct
4 Correct 459 ms 12868 KB Output is correct
5 Correct 148 ms 8468 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 13480 KB Output is correct
2 Execution timed out 1082 ms 23404 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 11288 KB Output is correct
2 Execution timed out 1085 ms 16256 KB Time limit exceeded
3 Halted 0 ms 0 KB -