oj.uz

Submission #282647

# Submission time Handle Problem Language Result Execution time Memory
282647 2020-08-24T16:46:16 Z SamAnd Teams (IOI15_teams) C++17
77 / 100
 997 ms 524292 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 (pos == 0)
        return 0;
    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]));
}

const int M = 300;
int pp[N];
int p[M][N];

int qryy(int l1, int r1, int l2, int r2)
{
    if (r1 < M)
        return p[r1][r2] - p[r1][l2 - 1];
    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]);
    }

    for (int i = 1; i < M; ++i)
    {
        for (int j = 0; j < sz(v[i]); ++j)
            pp[v[i][j]]++;
        for (int j = 1; j <= n; ++j)
            p[i][j] = p[i][j - 1] + pp[j];
    }
}

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:133:29: warning: declaration of 'v' shadows a global declaration [-Wshadow]
  133 |     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 10 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 10 ms 14592 KB Output is correct
4 Correct 10 ms 14592 KB Output is correct
5 Correct 10 ms 14592 KB Output is correct
6 Correct 10 ms 14592 KB Output is correct
7 Correct 10 ms 14592 KB Output is correct
8 Correct 10 ms 14592 KB Output is correct
9 Correct 10 ms 14592 KB Output is correct
10 Correct 10 ms 14592 KB Output is correct
11 Correct 10 ms 14592 KB Output is correct
12 Correct 10 ms 14592 KB Output is correct
13 Correct 10 ms 14592 KB Output is correct
14 Correct 11 ms 14592 KB Output is correct
15 Correct 10 ms 14720 KB Output is correct
16 Correct 10 ms 14592 KB Output is correct
17 Correct 9 ms 14464 KB Output is correct
18 Correct 10 ms 14464 KB Output is correct
19 Correct 10 ms 14464 KB Output is correct
20 Correct 9 ms 14464 KB Output is correct
21 Correct 10 ms 14464 KB Output is correct
22 Correct 9 ms 14464 KB Output is correct
23 Correct 10 ms 14464 KB Output is correct
24 Correct 10 ms 14464 KB Output is correct
25 Correct 9 ms 14464 KB Output is correct
26 Correct 9 ms 14464 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 156168 KB Output is correct
2 Correct 228 ms 156244 KB Output is correct
3 Correct 251 ms 156152 KB Output is correct
4 Correct 243 ms 157176 KB Output is correct
5 Correct 201 ms 154616 KB Output is correct
6 Correct 190 ms 154744 KB Output is correct
7 Correct 187 ms 154616 KB Output is correct
8 Correct 190 ms 154616 KB Output is correct
9 Correct 183 ms 153840 KB Output is correct
10 Correct 181 ms 153712 KB Output is correct
11 Correct 181 ms 154996 KB Output is correct
12 Correct 187 ms 153720 KB Output is correct
13 Correct 197 ms 154996 KB Output is correct
14 Correct 199 ms 154824 KB Output is correct
15 Correct 220 ms 155640 KB Output is correct
16 Correct 222 ms 155768 KB Output is correct
17 Correct 189 ms 155004 KB Output is correct
18 Correct 188 ms 155000 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 156540 KB Output is correct
2 Correct 247 ms 156592 KB Output is correct
3 Correct 375 ms 159480 KB Output is correct
4 Correct 232 ms 156920 KB Output is correct
5 Correct 203 ms 155000 KB Output is correct
6 Correct 204 ms 154964 KB Output is correct
7 Correct 194 ms 155000 KB Output is correct
8 Correct 201 ms 155000 KB Output is correct
9 Correct 186 ms 153840 KB Output is correct
10 Correct 186 ms 154140 KB Output is correct
11 Correct 189 ms 155120 KB Output is correct
12 Correct 825 ms 153968 KB Output is correct
13 Correct 498 ms 155508 KB Output is correct
14 Correct 379 ms 157692 KB Output is correct
15 Correct 234 ms 156152 KB Output is correct
16 Correct 232 ms 156280 KB Output is correct
17 Correct 204 ms 155232 KB Output is correct
18 Correct 206 ms 155252 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 997 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -