Submission #1075283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075283		skittles1412	Teams (IOI15_teams)	C++17	34 / 100	4061 ms	158652 KiB

teams

#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 << ")";
}

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) {
        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);

        vector cnt(m, vector(m, 0));
        // int cnt[m][m] {};
        {
            int comp1[n + 1], comp2[n + 1];
            for (int i = 0, j = 0; i <= n; i++) {
                while (j + 1 < m && carr[j + 1].first < i) {
                    j++;
                }

                comp1[i] = j;
            }
            for (int i = 0, j = 0; i <= n; i++) {
                while (j + 1 < m && carr[j + 1].first <= i) {
                    j++;
                }

                comp2[i] = j;
            }
            dbg(vector(comp1, comp1 + n + 1));
            dbg(vector(comp2, comp2 + n + 1));

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

        vector va(m, vector(m + 1, 0));
        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] + cnt[i - 1][j];
            }
        }
        auto querya = [&](int x, int y) -> int {
            return va[x][y];
            int ans = 0;

            for (int i = 0; i < x; i++) {
                for (int j = y; j < m; j++) {
                    ans += cnt[i][j];
                }
            }

            return ans;
        };
        auto query2 = [&](int il, int ir) -> int {
            return querya(ir, ir) - querya(il, ir);
            int ans = 0;
            for (int i = il; i < ir; i++) {
                for (int j = ir; j < m; j++) {
                    ans += cnt[i][j];
                }
            }
            return ans;
        };

        vector dp(m, 0);

        for (int i = m - 1; i >= 0; i--) {
            for (int j = i + 1; j < m; j++) {
                dp[i] = min(dp[i], va[j][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 || true) {
            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 (stderr)

teams.cpp: In constructor 'Solver::Solver(const std::vector<std::pair<int, int> >&)':
teams.cpp:146:42: warning: declaration of 'arr' shadows a member of 'Solver' [-Wshadow]
  146 |     Solver(const vector<pair<int, int>>& arr)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:142:28: note: shadowed declaration is here
  142 |     vector<pair<int, int>> arr;
      |                            ^~~
teams.cpp: In constructor 'Solver::Solver(const std::vector<std::pair<int, int> >&)':
teams.cpp:146:42: warning: declaration of 'arr' shadows a member of 'Solver' [-Wshadow]
  146 |     Solver(const vector<pair<int, int>>& arr)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:142:28: note: shadowed declaration is here
  142 |     vector<pair<int, int>> arr;
      |                            ^~~
teams.cpp: In constructor 'Solver::Solver(const std::vector<std::pair<int, int> >&)':
teams.cpp:146:42: warning: declaration of 'arr' shadows a member of 'Solver' [-Wshadow]
  146 |     Solver(const vector<pair<int, int>>& arr)
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:142:28: note: shadowed declaration is here
  142 |     vector<pair<int, int>> arr;
      |                            ^~~
teams.cpp: In member function 'bool Solver::query2(std::vector<std::pair<int, int> >)':
teams.cpp:215:14: warning: variable 'query2' set but not used [-Wunused-but-set-variable]
  215 |         auto query2 = [&](int il, int ir) -> int {
      |              ^~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23