oj.uz

Submission #99157

# Submission time Handle Problem Language Result Execution time Memory
99157 2019-02-28T23:38:37 Z eriksuenderhauf Teams (IOI15_teams) C++11
100 / 100
 3091 ms 182648 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "teams.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
int dp[MAXN];
int L[MAXN*50], R[MAXN*50], tree[MAXN*50];
int cnt = 0, m = 0, n = 0, root[MAXN*50];
vi pos, d, arr[MAXN];

int create(int k) {
    int ret = cnt++;
    tree[ret] = tree[k];
    L[ret] = L[k], R[ret] = R[k];
    return ret;
}

int qry(int l, int r, int k, int x, int y) {
    if (y < l || r < x) return 0;
    if (x <= l && r <= y)
        return tree[k];
    int mi = (l + r) / 2;
    return qry(l, mi, L[k], x, y) + qry(mi + 1, r, R[k], x, y);
}

int upd(int l, int r, int k, int x, int v) {
    if (r < x || x < l) return k;
    int nk = create(k);
    if (x <= l && r <= x) {
        tree[nk] += v;
        return nk;
    }
    int mi = (l + r) / 2;
    L[nk] = upd(l, mi, L[nk], x, v);
    R[nk] = upd(mi + 1, r, R[nk], x, v);
    tree[nk] = tree[L[nk]] + tree[R[nk]];
    return nk;
}

int build(int l, int r) {
    int cur = cnt++;
    if (l == r)
        return cur;
    int mi = (l + r) / 2;
    L[cur] = build(l, mi);
    R[cur] = build(mi + 1, r);
    tree[cur] = tree[L[cur]] + tree[R[cur]];
    return cur;
}

void init(int n, int a[], int b[]) {
    ::n = n;
    for (int i = 0; i < n; i++)
        arr[a[i] - 1].pb(b[i]);
    root[n] = build(0, n+1);
    for (int i = n - 1; i >= 0; i--) {
        root[i] = root[i + 1];
        for (int j: arr[i])
            root[i] = upd(0, n+1, root[i], j, 1);
    }
}

int gt(int x, int y) {
    int lo = y, hi = m + 1;
    while (lo < hi) {
        int mi = (lo + hi) / 2;
        if (dp[x] + qry(0, n+1, root[pos[x]], 0, pos[mi] - 1) + pos[mi] >= dp[y] + qry(0, n+1, root[pos[y]], 0, pos[mi] - 1) + pos[mi])
            hi = mi;
        else
            lo = mi + 1;
    }
    return lo;
}

int can(int m, int k[]) {
    ::m = m;
    pos = {0};
    for (int i = 0; i < m; i++)
        pos.pb(k[i]);
    sort(pos.begin(), pos.end());
    d.clear();
    int curCnt = 0;
    for (int i = 0; i <= m; i++) {
        if (i > 0) {
            while (d.size() > 1 && gt(d[d.size()-2], d.back()) <= i)
                d.pop_back();
            dp[i] = dp[d.back()] + qry(0, n+1, root[pos[d.back()]], 0, pos[i] - 1) + pos[i];
        }
        curCnt = max(curCnt, dp[i] + qry(0, n+1, root[pos[i]], 0, n));
        while (d.size() > 1 && gt(d[d.size()-2], d.back()) <= gt(d.back(), i))
            d.pop_back();
        d.pb(i);
    }
    if (curCnt > n)
        return 0;
    return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:61:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void init(int n, int a[], int b[]) {
                                  ^
teams.cpp:18:21: note: shadowed declaration is here
 int cnt = 0, m = 0, n = 0, root[MAXN*50];
                     ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:85:23: warning: declaration of 'm' shadows a global declaration [-Wshadow]
 int can(int m, int k[]) {
                       ^
teams.cpp:18:14: note: shadowed declaration is here
 int cnt = 0, m = 0, n = 0, root[MAXN*50];
              ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 25 ms 23808 KB Output is correct
3 Correct 26 ms 23936 KB Output is correct
4 Correct 33 ms 23928 KB Output is correct
5 Correct 26 ms 23800 KB Output is correct
6 Correct 50 ms 24056 KB Output is correct
7 Correct 26 ms 23936 KB Output is correct
8 Correct 32 ms 23920 KB Output is correct
9 Correct 27 ms 23936 KB Output is correct
10 Correct 25 ms 23928 KB Output is correct
11 Correct 27 ms 23896 KB Output is correct
12 Correct 27 ms 23808 KB Output is correct
13 Correct 31 ms 23936 KB Output is correct
14 Correct 26 ms 23936 KB Output is correct
15 Correct 25 ms 23808 KB Output is correct
16 Correct 30 ms 23936 KB Output is correct
17 Correct 28 ms 23808 KB Output is correct
18 Correct 29 ms 23936 KB Output is correct
19 Correct 26 ms 23936 KB Output is correct
20 Correct 27 ms 23808 KB Output is correct
21 Correct 27 ms 23796 KB Output is correct
22 Correct 27 ms 23936 KB Output is correct
23 Correct 25 ms 23808 KB Output is correct
24 Correct 25 ms 23808 KB Output is correct
25 Correct 28 ms 23928 KB Output is correct
26 Correct 25 ms 23856 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 50460 KB Output is correct
2 Correct 152 ms 50376 KB Output is correct
3 Correct 149 ms 50296 KB Output is correct
4 Correct 1099 ms 51896 KB Output is correct
5 Correct 68 ms 49220 KB Output is correct
6 Correct 60 ms 49144 KB Output is correct
7 Correct 63 ms 49144 KB Output is correct
8 Correct 67 ms 49060 KB Output is correct
9 Correct 341 ms 50032 KB Output is correct
10 Correct 164 ms 49648 KB Output is correct
11 Correct 70 ms 49376 KB Output is correct
12 Correct 64 ms 49392 KB Output is correct
13 Correct 78 ms 49524 KB Output is correct
14 Correct 104 ms 49908 KB Output is correct
15 Correct 135 ms 50168 KB Output is correct
16 Correct 116 ms 50100 KB Output is correct
17 Correct 94 ms 49372 KB Output is correct
18 Correct 66 ms 49528 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 50772 KB Output is correct
2 Correct 541 ms 50776 KB Output is correct
3 Correct 339 ms 53624 KB Output is correct
4 Correct 1036 ms 51700 KB Output is correct
5 Correct 243 ms 49528 KB Output is correct
6 Correct 365 ms 49528 KB Output is correct
7 Correct 770 ms 49784 KB Output is correct
8 Correct 396 ms 49540 KB Output is correct
9 Correct 312 ms 50160 KB Output is correct
10 Correct 619 ms 49904 KB Output is correct
11 Correct 585 ms 49908 KB Output is correct
12 Correct 483 ms 49856 KB Output is correct
13 Correct 461 ms 50072 KB Output is correct
14 Correct 430 ms 52036 KB Output is correct
15 Correct 306 ms 50780 KB Output is correct
16 Correct 304 ms 50708 KB Output is correct
17 Correct 319 ms 49912 KB Output is correct
18 Correct 293 ms 49780 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2015 ms 169324 KB Output is correct
2 Correct 1992 ms 175968 KB Output is correct
3 Correct 1474 ms 182648 KB Output is correct
4 Correct 3091 ms 177208 KB Output is correct
5 Correct 887 ms 166904 KB Output is correct
6 Correct 878 ms 167032 KB Output is correct
7 Correct 1842 ms 167160 KB Output is correct
8 Correct 1036 ms 166968 KB Output is correct
9 Correct 1676 ms 168680 KB Output is correct
10 Correct 1688 ms 165096 KB Output is correct
11 Correct 1501 ms 165552 KB Output is correct
12 Correct 1207 ms 166460 KB Output is correct
13 Correct 1688 ms 169816 KB Output is correct
14 Correct 1648 ms 178244 KB Output is correct
15 Correct 1253 ms 174572 KB Output is correct
16 Correct 1176 ms 174328 KB Output is correct
17 Correct 889 ms 168936 KB Output is correct
18 Correct 813 ms 168868 KB Output is correct