oj.uz

Submission #99577

# Submission time Handle Problem Language Result Execution time Memory
99577 2019-03-05T11:15:22 Z eriksuenderhauf Teams (IOI15_teams) C++11
100 / 100
 2666 ms 182732 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;
        // a > k_x, b < k_mi; a > k_y, b < k_mi
        if (dp[x] + qry(0, n+1, root[pos[x]], 0, pos[mi] - 1) >= dp[y] + qry(0, n+1, root[pos[y]], 0, pos[mi] - 1))
            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:86: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 31 ms 23808 KB Output is correct
2 Correct 29 ms 23808 KB Output is correct
3 Correct 26 ms 23936 KB Output is correct
4 Correct 28 ms 23808 KB Output is correct
5 Correct 28 ms 23808 KB Output is correct
6 Correct 53 ms 24056 KB Output is correct
7 Correct 28 ms 23936 KB Output is correct
8 Correct 32 ms 23928 KB Output is correct
9 Correct 31 ms 23936 KB Output is correct
10 Correct 30 ms 23936 KB Output is correct
11 Correct 28 ms 23808 KB Output is correct
12 Correct 29 ms 23808 KB Output is correct
13 Correct 27 ms 23808 KB Output is correct
14 Correct 31 ms 23936 KB Output is correct
15 Correct 26 ms 23936 KB Output is correct
16 Correct 26 ms 23808 KB Output is correct
17 Correct 29 ms 23860 KB Output is correct
18 Correct 28 ms 23804 KB Output is correct
19 Correct 29 ms 23928 KB Output is correct
20 Correct 28 ms 23776 KB Output is correct
21 Correct 26 ms 23808 KB Output is correct
22 Correct 27 ms 23808 KB Output is correct
23 Correct 26 ms 23852 KB Output is correct
24 Correct 26 ms 23808 KB Output is correct
25 Correct 26 ms 23900 KB Output is correct
26 Correct 28 ms 23808 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 50016 KB Output is correct
2 Correct 145 ms 50012 KB Output is correct
3 Correct 142 ms 50156 KB Output is correct
4 Correct 871 ms 51580 KB Output is correct
5 Correct 63 ms 49500 KB Output is correct
6 Correct 61 ms 49448 KB Output is correct
7 Correct 68 ms 49604 KB Output is correct
8 Correct 78 ms 49488 KB Output is correct
9 Correct 280 ms 50428 KB Output is correct
10 Correct 187 ms 49904 KB Output is correct
11 Correct 87 ms 49648 KB Output is correct
12 Correct 67 ms 49648 KB Output is correct
13 Correct 86 ms 50188 KB Output is correct
14 Correct 93 ms 50416 KB Output is correct
15 Correct 145 ms 51064 KB Output is correct
16 Correct 125 ms 51040 KB Output is correct
17 Correct 70 ms 50220 KB Output is correct
18 Correct 85 ms 50168 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 50296 KB Output is correct
2 Correct 604 ms 50448 KB Output is correct
3 Correct 301 ms 53240 KB Output is correct
4 Correct 887 ms 52776 KB Output is correct
5 Correct 271 ms 50376 KB Output is correct
6 Correct 294 ms 50448 KB Output is correct
7 Correct 759 ms 50404 KB Output is correct
8 Correct 367 ms 50452 KB Output is correct
9 Correct 286 ms 50544 KB Output is correct
10 Correct 641 ms 50144 KB Output is correct
11 Correct 546 ms 50212 KB Output is correct
12 Correct 378 ms 50432 KB Output is correct
13 Correct 415 ms 51188 KB Output is correct
14 Correct 421 ms 53496 KB Output is correct
15 Correct 266 ms 51832 KB Output is correct
16 Correct 275 ms 51736 KB Output is correct
17 Correct 257 ms 50808 KB Output is correct
18 Correct 299 ms 50932 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1893 ms 168948 KB Output is correct
2 Correct 1944 ms 175948 KB Output is correct
3 Correct 1448 ms 182732 KB Output is correct
4 Correct 2666 ms 177304 KB Output is correct
5 Correct 911 ms 167004 KB Output is correct
6 Correct 860 ms 167092 KB Output is correct
7 Correct 1955 ms 167044 KB Output is correct
8 Correct 987 ms 167160 KB Output is correct
9 Correct 1567 ms 168552 KB Output is correct
10 Correct 1658 ms 164900 KB Output is correct
11 Correct 1268 ms 165480 KB Output is correct
12 Correct 1189 ms 166372 KB Output is correct
13 Correct 1745 ms 169736 KB Output is correct
14 Correct 1754 ms 178164 KB Output is correct
15 Correct 1075 ms 174168 KB Output is correct
16 Correct 973 ms 174328 KB Output is correct
17 Correct 833 ms 168860 KB Output is correct
18 Correct 818 ms 168740 KB Output is correct