oj.uz

Submission #1075285

# Submission time Handle Problem Language Result Execution time Memory
1075285 2024-08-26T01:04:59 Z skittles1412 Teams (IOI15_teams) C++17
100 / 100
 1166 ms 158692 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

inline void init_io() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
}

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

template <typename T>
struct PSA {
    int n;
    vector<T> psum;

    template <typename U>
    PSA(const vector<U>& arr) : n(sz(arr)), psum(n + 1) {
        for (int i = 0; i < n; i++) {
            psum[i + 1] = psum[i] + arr[i];
        }
    }

    T query(int l, int r) const {
        return psum[r] - psum[l];
    }
};

template <typename T>
bool on(T mask, int bit) {
    return (mask >> bit) & 1;
}

template <typename T>
vector<T> iota(int n, T x) {
    vector<T> arr(n);
    iota(begin(arr), end(arr), x);
    return arr;
}

template <typename T>
T reversed(T arr) {
    reverse(begin(arr), end(arr));
    return arr;
}

template <typename A, typename B>
ostream& operator<<(ostream& out, const pair<A, B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}

template <typename Cb>
struct CmpByKey {
    Cb cb;

    CmpByKey(Cb cb) : cb(cb) {}

    template <typename T>
    bool operator()(const T& a, const T& b) const {
        return cb(a) < cb(b);
    }
};

namespace st1 {

struct Node {
    int lc, rc, v;
} heap[(500 << 20) / sizeof(Node)];
int n, hind = 1;

void update(int& o, int l, int r, int ind, int x) {
    heap[hind] = heap[o];
    o = hind++;
    if (l == r) {
        heap[o].v += x;
        return;
    }

    int mid = (l + r) / 2;
    if (ind <= mid) {
        update(heap[o].lc, l, mid, ind, x);
    } else {
        update(heap[o].rc, mid + 1, r, ind, x);
    }

    heap[o].v = heap[heap[o].lc].v + heap[heap[o].rc].v;
}

void update(int& root, int ind, int x) {
    update(root, 0, n - 1, ind, x);
}

int query_pref(int o, int qr) {
    int ans = 0, l = 0, r = n - 1;

    while (true) {
        if (!o) {
            return ans;
        } else if (r <= qr) {
            return ans + heap[o].v;
        }

        int mid = (l + r) / 2;
        if (qr <= mid) {
            o = heap[o].lc;
            r = mid;
        } else {
            ans += heap[heap[o].lc].v;
            l = mid + 1;
            o = heap[o].rc;
        }
    }
}

}  // namespace st1

struct Solver {
    int n;
    vector<pair<int, int>> arr;
    vector<int> roots;

    Solver() {}
    Solver(const vector<pair<int, int>>& _arr)
        : n(sz(_arr)), arr(_arr), roots(n + 1) {
        sort(begin(arr), end(arr), CmpByKey([&](const auto& a) -> int {
            return a.first;
        }));
        st1::n = n + 5;

        vector<vector<int>> evts(n + 1);
        for (auto& [l, r] : arr) {
            evts[r].push_back(l);
        }

        int root = 0;
        for (int i = n; i >= 0; i--) {
            for (auto& a : evts[i]) {
                st1::update(root, a, +1);
            }

            roots[i] = root;
        }
    }

    bool query2(vector<pair<int, int>> carr) {
        carr.insert(begin(carr), pair {-1, 0});
        int m = sz(carr);

        int va[m + 1][m + 1] {};
        {
            int comp1[n + 10], comp2[n + 10];
            for (int i = 0; i < m; i++) {
                int cr = i + 1 < m ? carr[i + 1].first : n + 5;
                fill(comp1 + carr[i].first + 1, comp1 + cr + 1, i + 1);
                fill(comp2 + max(0, carr[i].first), comp2 + cr, i);
            }

            for (auto& [l, r] : arr) {
                va[comp1[l]][comp2[r]]++;
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = m - 1; j >= 0; j--) {
                va[i][j] = va[i - 1][j] + va[i][j + 1] - va[i - 1][j + 1] +
                           va[i][j];
            }
        }
        int va2[m];
        for (int i = 0; i < m; i++) {
            va2[i] = va[i][i];
        }

        int dp[m] {};

        for (int i = m - 1; i >= 0; i--) {
            for (int j = i + 1; j < m; j++) {
                dp[i] = min(dp[i], va2[j] - va[i][j] + dp[j] - carr[j].second);
            }
        }

        return dp[0] >= 0;
    }

    bool query(vector<int> qarr) {
        if (accumulate(begin(qarr), end(qarr), long(0)) > n) {
            return false;
        }

        vector<pair<int, int>> carr;
        sort(begin(qarr), end(qarr));
        for (int i = 0; i < sz(qarr);) {
            int cl = i;
            for (; i < sz(qarr) && qarr[cl] == qarr[i]; i++)
                ;
            carr.emplace_back(qarr[cl], (i - cl) * qarr[cl]);
        }

        if (sz(carr) > 400) {
            return query2(carr);
        }
        carr.insert(begin(carr), pair {-1, 0});
        int m = sz(carr);

        vector dp(m, 0);
        for (int j = m - 1; j >= 1; j--) {
            int qr = carr[j].first, cv = st1::query_pref(roots[qr], qr);

            for (int i = 0; i < j; i++) {
                dp[i] =
                    min(dp[i], cv - st1::query_pref(roots[qr], carr[i].first) +
                                   dp[j] - carr[j].second);
            }
        }

        return dp[0] >= 0;
    }
} solver;

void init(int n, int arra[], int arrb[]) {
    solver = Solver([&]() {
        vector<pair<int, int>> cv;

        for (int i = 0; i < n; i++) {
            cv.emplace_back(arra[i], arrb[i]);
        }

        return cv;
    }());
}

int can(int m, int arr[]) {
    return solver.query(vector(arr, arr + m));
}

Compilation message

teams.cpp: In constructor 'CmpByKey<Cb>::CmpByKey(Cb)':
teams.cpp:91:17: warning: declaration of 'cb' shadows a member of 'CmpByKey<Cb>' [-Wshadow]
   91 |     CmpByKey(Cb cb) : cb(cb) {}
      |              ~~~^~
teams.cpp:89:8: note: shadowed declaration is here
   89 |     Cb cb;
      |        ^~
teams.cpp: In instantiation of 'CmpByKey<Cb>::CmpByKey(Cb) [with Cb = Solver::Solver(const std::vector<std::pair<int, int> >&)::<lambda(const auto:23&)>]':
teams.cpp:162:10:   required from here
teams.cpp:91:17: warning: declaration of 'cb' shadows a member of 'CmpByKey<Solver::Solver(const std::vector<std::pair<int, int> >&)::<lambda(const auto:23&)> >' [-Wshadow]
   91 |     CmpByKey(Cb cb) : cb(cb) {}
      |              ~~~^~
teams.cpp:89:8: note: shadowed declaration is here
   89 |     Cb cb;
      |        ^~
teams.cpp:91:17: warning: declaration of 'cb' shadows a member of 'CmpByKey<Solver::Solver(const std::vector<std::pair<int, int> >&)::<lambda(const auto:23&)> >' [-Wshadow]
   91 |     CmpByKey(Cb cb) : cb(cb) {}
      |              ~~~^~
teams.cpp:89:8: note: shadowed declaration is here
   89 |     Cb cb;
      |        ^~
teams.cpp:91:17: warning: declaration of 'cb' shadows a member of 'CmpByKey<Solver::Solver(const std::vector<std::pair<int, int> >&)::<lambda(const auto:23&)> >' [-Wshadow]
   91 |     CmpByKey(Cb cb) : cb(cb) {}
      |              ~~~^~
teams.cpp:89:8: note: shadowed declaration is here
   89 |     Cb cb;
      |        ^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 600 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 29024 KB Output is correct
2 Correct 51 ms 29124 KB Output is correct
3 Correct 53 ms 29128 KB Output is correct
4 Correct 56 ms 29380 KB Output is correct
5 Correct 30 ms 27588 KB Output is correct
6 Correct 30 ms 27592 KB Output is correct
7 Correct 29 ms 27592 KB Output is correct
8 Correct 30 ms 27588 KB Output is correct
9 Correct 28 ms 28368 KB Output is correct
10 Correct 28 ms 28112 KB Output is correct
11 Correct 25 ms 28100 KB Output is correct
12 Correct 27 ms 28112 KB Output is correct
13 Correct 32 ms 28112 KB Output is correct
14 Correct 34 ms 28624 KB Output is correct
15 Correct 46 ms 28972 KB Output is correct
16 Correct 44 ms 28872 KB Output is correct
17 Correct 29 ms 27856 KB Output is correct
18 Correct 29 ms 28104 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 29384 KB Output is correct
2 Correct 364 ms 29384 KB Output is correct
3 Correct 95 ms 29384 KB Output is correct
4 Correct 50 ms 29384 KB Output is correct
5 Correct 160 ms 27848 KB Output is correct
6 Correct 177 ms 27848 KB Output is correct
7 Correct 161 ms 27852 KB Output is correct
8 Correct 171 ms 27672 KB Output is correct
9 Correct 27 ms 28348 KB Output is correct
10 Correct 31 ms 28128 KB Output is correct
11 Correct 38 ms 28104 KB Output is correct
12 Correct 310 ms 28360 KB Output is correct
13 Correct 104 ms 28480 KB Output is correct
14 Correct 92 ms 29128 KB Output is correct
15 Correct 67 ms 29324 KB Output is correct
16 Correct 65 ms 29128 KB Output is correct
17 Correct 51 ms 28112 KB Output is correct
18 Correct 47 ms 28356 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 157360 KB Output is correct
2 Correct 1166 ms 157220 KB Output is correct
3 Correct 523 ms 157112 KB Output is correct
4 Correct 350 ms 158692 KB Output is correct
5 Correct 729 ms 149692 KB Output is correct
6 Correct 726 ms 149696 KB Output is correct
7 Correct 727 ms 149692 KB Output is correct
8 Correct 720 ms 149692 KB Output is correct
9 Correct 139 ms 151904 KB Output is correct
10 Correct 135 ms 149948 KB Output is correct
11 Correct 313 ms 150416 KB Output is correct
12 Correct 912 ms 150972 KB Output is correct
13 Correct 398 ms 152384 KB Output is correct
14 Correct 508 ms 157180 KB Output is correct
15 Correct 317 ms 156860 KB Output is correct
16 Correct 320 ms 157096 KB Output is correct
17 Correct 209 ms 152504 KB Output is correct
18 Correct 213 ms 153020 KB Output is correct