Submission #586024

#	Time	Username	Problem	Language	Result	Execution time	Memory
586024		snokes	Teams (IOI15_teams)	C++17	34 / 100	4025 ms	524288 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<set<pair<int, int>>> S;
    int N;
    SegTree(int _N)
    {
        N = 1;
        while(N < _N) N *= 2;
        S = vt<set<pair<int, int>>>(2 * N);
    }

    void upd(int i, int x)
    {
        int u = i + N - 1;
        assert(S[u].size() <= 1);
        auto prev = S[u].empty() ? make_pair(INF, -1) : *S[u].begin();
        auto current = make_pair(x, i);
        for( ; u > 0; u /= 2)
        {
            S[u].erase(prev);
            S[u].insert(current);
        }
    }

    void del(int i)
    {
        upd(i, INF);
    }

    pair<int, int> qry(int l, int r, int x, int a, int b, int i)
    {
        if(l <= a && b <= r)
        {
            auto it = S[i].lower_bound(make_pair(x, -1));
            if(it == S[i].end()) return make_pair(INF, -1);
            return *it;
        }
        if(r < a || b < l) return make_pair(INF, -1);
        int m = (a + b) / 2;
        return min(qry(l, r, x, a, m, 2 * i), qry(l, r, x, m + 1, b, 2 * i + 1));
    }
    pair<int, int> qry(int l, int r, int x) {return qry(l, r, x, 1, N, 1);}
};

vt<pair<int, int>> v;
int N;

SegTree s(1);

void init(int _N, int A[], int B[])
{
    N = _N;
    v = vt<pair<int, int>>(N);
    for(int i = 0; i < N; i++)
    {
        v[i].first = A[i];
        v[i].second = B[i];
    }

    sort(v.begin(), v.end());
    s = SegTree(N);
    for(int i = 0; i < N; i++)
    {
        s.upd(i + 1, v[i].second);
    }
}

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

    long long sum = 0;
    for(int i = 0; i < M; i++) sum += K[i];

    if(sum > N)
    {
        return 0;
    }


    vt<pair<int, int>> changed;
    bool ok = 1;
    for(int i = 0; i < M && ok; i++)
    {
        int j = upper_bound(v.begin(), v.end(), make_pair(K[i] + 1, -1)) - v.begin() - 1;
        //while(j + 1 < N && v[j + 1].first <= K[i]) j++;
        int rem = K[i];
        while(rem > 0)
        {
            auto cur = s.qry(1, j + 1, K[i]);
            if(cur.second == -1 || cur.first == INF)
            {
                ok = 0;
                break;
            }
            rem--;
            assert(1 <= cur.second && cur.second <= N);
            changed.push_back(make_pair(cur.second, cur.first));
            s.del(cur.second);
        }
    }

    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
1
2 1 3
*/

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

*/

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:105:86: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  105 |         int j = upper_bound(v.begin(), v.end(), make_pair(K[i] + 1, -1)) - v.begin() - 1;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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