oj.uz

Submission #99156

# Submission time Handle Problem Language Result Execution time Memory
99156 2019-02-28T23:36:19 Z eriksuenderhauf Teams (IOI15_teams) C++11
77 / 100
 1222 ms 319924 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*10], R[MAXN*10], tree[MAXN*10];
int cnt = 0, m = 0, n = 0, root[MAXN*10];
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*10];
                     ^
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*10];
              ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23928 KB Output is correct
2 Correct 28 ms 23808 KB Output is correct
3 Correct 24 ms 23936 KB Output is correct
4 Correct 31 ms 23800 KB Output is correct
5 Correct 25 ms 23808 KB Output is correct
6 Correct 69 ms 24088 KB Output is correct
7 Correct 24 ms 23936 KB Output is correct
8 Correct 26 ms 23808 KB Output is correct
9 Correct 26 ms 23936 KB Output is correct
10 Correct 29 ms 23804 KB Output is correct
11 Correct 29 ms 23928 KB Output is correct
12 Correct 41 ms 23936 KB Output is correct
13 Correct 26 ms 23808 KB Output is correct
14 Correct 24 ms 23808 KB Output is correct
15 Correct 25 ms 23928 KB Output is correct
16 Correct 25 ms 23928 KB Output is correct
17 Correct 25 ms 23808 KB Output is correct
18 Correct 26 ms 23936 KB Output is correct
19 Correct 29 ms 23936 KB Output is correct
20 Correct 23 ms 23936 KB Output is correct
21 Correct 28 ms 23808 KB Output is correct
22 Correct 23 ms 23928 KB Output is correct
23 Correct 22 ms 23808 KB Output is correct
24 Correct 24 ms 23928 KB Output is correct
25 Correct 23 ms 23928 KB Output is correct
26 Correct 25 ms 23936 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 51064 KB Output is correct
2 Correct 140 ms 51244 KB Output is correct
3 Correct 161 ms 51284 KB Output is correct
4 Correct 1222 ms 52724 KB Output is correct
5 Correct 63 ms 49656 KB Output is correct
6 Correct 67 ms 49600 KB Output is correct
7 Correct 72 ms 49656 KB Output is correct
8 Correct 68 ms 49528 KB Output is correct
9 Correct 353 ms 50672 KB Output is correct
10 Correct 169 ms 49776 KB Output is correct
11 Correct 77 ms 49776 KB Output is correct
12 Correct 63 ms 49776 KB Output is correct
13 Correct 67 ms 50164 KB Output is correct
14 Correct 92 ms 50388 KB Output is correct
15 Correct 125 ms 50936 KB Output is correct
16 Correct 128 ms 51020 KB Output is correct
17 Correct 72 ms 50168 KB Output is correct
18 Correct 63 ms 50304 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 52088 KB Output is correct
2 Correct 604 ms 52216 KB Output is correct
3 Correct 397 ms 55220 KB Output is correct
4 Correct 1193 ms 52852 KB Output is correct
5 Correct 344 ms 50368 KB Output is correct
6 Correct 316 ms 50308 KB Output is correct
7 Correct 759 ms 50424 KB Output is correct
8 Correct 373 ms 50496 KB Output is correct
9 Correct 318 ms 50416 KB Output is correct
10 Correct 759 ms 50288 KB Output is correct
11 Correct 599 ms 50400 KB Output is correct
12 Correct 585 ms 50552 KB Output is correct
13 Correct 502 ms 51228 KB Output is correct
14 Correct 433 ms 53500 KB Output is correct
15 Correct 328 ms 51960 KB Output is correct
16 Correct 359 ms 51880 KB Output is correct
17 Correct 510 ms 50936 KB Output is correct
18 Correct 517 ms 50876 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1043 ms 319924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -