Submission #585122

#	Time	Username	Problem	Language	Result	Execution time	Memory
585122		snokes	Teams (IOI15_teams)	C++17	0 / 100	4051 ms	35148 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define vt vector

#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL

const int INF = 1e9 + 5;

struct SegTree
{
    vt<int> S;
    int N;
    SegTree(int _N)
    {
        N = 1;
        while(N < _N) N *= 2;
        S = vt<int>(2 * N, -INF);
    }

    void upd(int i, int x)
    {
        int u = i + N - 1;
        S[u] = x;
        for(u /= 2; u > 0; u /= 2) S[u] = max(S[2 * u], S[2 * u + 1]);
    }

    pair<int, int> findFirst(int x, int i)
    {
        if(i >= N) return make_pair(S[i], i - N + 1);
        if(S[2 * i] >= x) return findFirst(x, 2 * i);
        else return findFirst(x, 2 * i + 1);
    }
};

const int mxN = 5e5 + 5;
vector<int> until[mxN];
int val[mxN];
int N;

SegTree s(1);

void init(int _N, int A[], int B[])
{
    N = _N;
    for(int i = 0; i < N; i++)
    {
        until[A[i]].push_back(B[i]);
    }
    for(int i = 0; i < mxN; i++) sort(until[i].begin(), until[i].end());
    s = SegTree(N);
    for(int i = 0, j = 1; i < mxN; i++)
    {
        for(int x : until[i])
        {
            s.upd(j, x);
            val[j] = i;
            j++;
        }
    }
}

int can(int M, int K[]) {
    sort(K, K + M);


    vt<pair<int, int>> changed;
    bool ok = 1;
    for(int i = 0; i < M && ok; i++)
    {
        int rem = K[i];
        while(rem > 0)
        {
            auto cur = s.findFirst(K[i], 1);
            if(cur.first < K[i] || cur.second == -1 || val[cur.second] > K[i])
            {
                ok = 0;
                break;
            }
            rem--;
            assert(1 <= cur.second && cur.second <= N);
            changed.push_back(make_pair(cur.second, cur.first));
            s.upd(cur.second, -INF);
        }
    }

    for(auto [a, b] : changed) s.upd(a, b);

    return ok;
}

/*
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _N;
    cin >> _N;
    int A[_N], B[_N];
    for(int i = 0; i < _N; i++) cin >> A[i] >> B[i];
    init(_N, A, B);
    int Q;
    cin >> Q;
    for(int _i = 0; _i < Q; _i++)
    {
        int M;
        cin >> M;
        int sizes[M];
        for(int i = 0; i < M; i++) cin >> sizes[i];
        cout << can(M, sizes) << "\n";
    }
}
*/

/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1

*/

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