oj.uz

Submission #282576

# Submission time Handle Problem Language Result Execution time Memory
282576 2020-08-24T15:12:43 Z SamAnd Teams (IOI15_teams) C++17
77 / 100
 4000 ms 156556 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
const int N = 500005, L = 20;

struct ban
{
    int l, r;
};
bool operator<(const ban& a, const ban& b)
{
    return a.l < b.l;
}

int n;
ban a[N];

vector<int> v[N];

int root[N];

int z;
int t[N * L];
int ul[N * L], ur[N * L];

int ubd(int tl, int tr, int x, int pos)
{
    int ypos = ++z;
    ul[ypos] = ul[pos];
    ur[ypos] = ur[pos];
    t[ypos] = t[pos];
    t[ypos]++;
    if (tl == tr)
        return ypos;
    int m = (tl + tr) / 2;
    if (x <= m)
    {
        ul[ypos] = ubd(tl, m, x, ul[pos]);
    }
    else
    {
        ur[ypos] = ubd(m + 1, tr, x, ur[pos]);
    }
    return ypos;
}

int qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    return (qry(tl, m, l, min(m, r), ul[pos]) +
            qry(m + 1, tr, max(m + 1, l), r, ur[pos]));
}

int qryy(int l1, int r1, int l2, int r2)
{
    return qry(1, n, l2, r2, root[r1]) - qry(1, n, l2, r2, root[l1 - 1]);
}

void init(int N_, int A[], int B[])
{
    n = N_;
    for (int i = 0; i < n; ++i)
    {
        a[i].l = A[i];
        a[i].r = B[i];
        v[a[i].l].push_back(a[i].r);
    }
    sort(a, a + n);

    for (int i = 1; i <= n; ++i)
    {
        root[i] = root[i - 1];
        for (int j = 0; j < sz(v[i]); ++j)
            root[i] = ubd(1, n, v[i][j], root[i]);
    }
}

int m;
int b[N];

int can(int M_, int K[])
{
    m = M_;
    for (int i = 0; i < m; ++i)
        b[i] = K[i];
    sort(b, b + m);
    ll sum = 0;
    for (int i = 0; i < m; ++i)
        sum += b[i];
    if (sum > n)
        return 0;

    /*multiset<int> s;
    int j = 0;
    for (int i = 0; i < m; ++i)
    {
        while (j < n && a[j].l <= b[i])
            s.insert(a[j++].r);
        while (!s.empty() && *s.begin() < b[i])
            s.erase(s.begin());
        if (sz(s) < b[i])
            return 0;
        for (int j = 0; j < b[i]; ++j)
            s.erase(s.begin());
    }*/

    vector<pair<int, int> > v;
    v.push_back(m_p(b[0], b[0]));
    for (int i = 1; i < m; ++i)
    {
        if (b[i] == v.back().fi)
            v.back().se += b[i];
        else
            v.push_back(m_p(b[i], b[i]));
    }

    vector<int> h;
    h.assign(sz(v), 0);

    for (int i = 0; i < sz(v); ++i)
    {
        for (int j = i; j < sz(v); ++j)
        {
            int nx;
            if (j == sz(v) - 1)
                nx = n + 1;
            else
                nx = v[j + 1].fi;
            int q = qryy(1, v[i].fi, v[j].fi, nx - 1) - h[j];
            if (q < v[i].se)
            {
                h[j] += q;
                v[i].se -= q;
            }
            else
            {
                h[j] += v[i].se;
                v[i].se = 0;
                break;
            }
        }
        if (v[i].se)
            return 0;
    }

    return 1;
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:117:29: warning: declaration of 'v' shadows a global declaration [-Wshadow]
  117 |     vector<pair<int, int> > v;
      |                             ^
teams.cpp:24:13: note: shadowed declaration is here
   24 | vector<int> v[N];
      |             ^

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 36600 KB Output is correct
2 Correct 89 ms 36708 KB Output is correct
3 Correct 90 ms 36580 KB Output is correct
4 Correct 86 ms 37384 KB Output is correct
5 Correct 44 ms 35448 KB Output is correct
6 Correct 45 ms 35448 KB Output is correct
7 Correct 43 ms 35448 KB Output is correct
8 Correct 44 ms 35432 KB Output is correct
9 Correct 38 ms 34672 KB Output is correct
10 Correct 38 ms 34672 KB Output is correct
11 Correct 49 ms 35696 KB Output is correct
12 Correct 42 ms 34552 KB Output is correct
13 Correct 50 ms 35828 KB Output is correct
14 Correct 60 ms 35312 KB Output is correct
15 Correct 93 ms 36472 KB Output is correct
16 Correct 75 ms 36472 KB Output is correct
17 Correct 44 ms 35832 KB Output is correct
18 Correct 46 ms 35960 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 37112 KB Output is correct
2 Correct 193 ms 37020 KB Output is correct
3 Correct 224 ms 40444 KB Output is correct
4 Correct 91 ms 38776 KB Output is correct
5 Correct 85 ms 37032 KB Output is correct
6 Correct 85 ms 37032 KB Output is correct
7 Correct 92 ms 36984 KB Output is correct
8 Correct 99 ms 37112 KB Output is correct
9 Correct 39 ms 35568 KB Output is correct
10 Correct 41 ms 35568 KB Output is correct
11 Correct 109 ms 36848 KB Output is correct
12 Correct 2400 ms 36052 KB Output is correct
13 Correct 511 ms 37876 KB Output is correct
14 Correct 279 ms 40184 KB Output is correct
15 Correct 133 ms 38520 KB Output is correct
16 Correct 128 ms 38520 KB Output is correct
17 Correct 91 ms 37624 KB Output is correct
18 Correct 84 ms 37492 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 148832 KB Output is correct
2 Correct 803 ms 148856 KB Output is correct
3 Correct 977 ms 156536 KB Output is correct
4 Correct 596 ms 156556 KB Output is correct
5 Correct 299 ms 147320 KB Output is correct
6 Correct 295 ms 147320 KB Output is correct
7 Correct 281 ms 147320 KB Output is correct
8 Correct 300 ms 147320 KB Output is correct
9 Correct 181 ms 141416 KB Output is correct
10 Correct 184 ms 145128 KB Output is correct
11 Correct 3688 ms 145908 KB Output is correct
12 Execution timed out 4029 ms 146336 KB Time limit exceeded
13 Halted 0 ms 0 KB -