Submission #586039

#	Time	Username	Problem	Language	Result	Execution time	Memory
586039		snokes	Teams (IOI15_teams)	C++17	34 / 100	4056 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;

const int mxN = 1 << 19;
set<pair<int, int>> S[2 * mxN];
pair<int, int> v[mxN];

void upd(int i, int x)
{
    int u = i + mxN - 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, mxN, 1);}


int N;

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

    sort(v, v + N);
    for(int i = 0; i < N; i++)
    {
        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, v + N, make_pair(K[i] + 1, -1)) - v - 1;
        int rem = K[i];
        while(rem > 0)
        {
            auto cur = 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.emplace_back(cur.second, cur.first);
            del(cur.second);
        }
    }

    for(auto [a, b] : changed) 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:89:68: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   89 |         int j = upper_bound(v, v + N, make_pair(K[i] + 1, -1)) - v - 1;
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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