oj.uz

Submission #99594

# Submission time Handle Problem Language Result Execution time Memory
99594 2019-03-05T13:33:39 Z eriksuenderhauf Teams (IOI15_teams) C++11
13 / 100
 1780 ms 174428 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);
    }
}

// index when y becomes more profitable than x
int gt(int x, int y) {
    int lo = y, hi = m + 1;
    while (lo < hi) { // find smallest index lo, s.t. dp[x] + students in interval (x,lo) >= dp[y] + students in interval (y,lo)
        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));
        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:87: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
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 25 ms 23808 KB Output is correct
3 Correct 27 ms 23808 KB Output is correct
4 Correct 23 ms 23808 KB Output is correct
5 Correct 24 ms 23936 KB Output is correct
6 Correct 34 ms 24064 KB Output is correct
7 Correct 25 ms 23936 KB Output is correct
8 Correct 25 ms 23680 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 25 ms 23936 KB Output is correct
11 Correct 27 ms 23936 KB Output is correct
12 Correct 28 ms 23808 KB Output is correct
13 Correct 25 ms 23936 KB Output is correct
14 Incorrect 25 ms 23872 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 50080 KB Output is correct
2 Correct 162 ms 49992 KB Output is correct
3 Correct 160 ms 49988 KB Output is correct
4 Correct 528 ms 51720 KB Output is correct
5 Correct 63 ms 49016 KB Output is correct
6 Correct 70 ms 48760 KB Output is correct
7 Correct 77 ms 48888 KB Output is correct
8 Correct 67 ms 48948 KB Output is correct
9 Correct 189 ms 49908 KB Output is correct
10 Correct 109 ms 49520 KB Output is correct
11 Correct 71 ms 49392 KB Output is correct
12 Correct 64 ms 49264 KB Output is correct
13 Correct 71 ms 49396 KB Output is correct
14 Correct 98 ms 49632 KB Output is correct
15 Correct 120 ms 50040 KB Output is correct
16 Correct 135 ms 50024 KB Output is correct
17 Correct 69 ms 49272 KB Output is correct
18 Correct 74 ms 49532 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 50392 KB Output is correct
2 Correct 277 ms 50364 KB Output is correct
3 Correct 328 ms 53368 KB Output is correct
4 Correct 548 ms 51876 KB Output is correct
5 Correct 268 ms 49272 KB Output is correct
6 Correct 262 ms 49272 KB Output is correct
7 Correct 476 ms 49272 KB Output is correct
8 Correct 369 ms 49360 KB Output is correct
9 Correct 145 ms 49904 KB Output is correct
10 Correct 434 ms 49776 KB Output is correct
11 Correct 258 ms 49648 KB Output is correct
12 Correct 238 ms 49692 KB Output is correct
13 Incorrect 302 ms 49872 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1440 ms 168488 KB Output is correct
2 Correct 1339 ms 168384 KB Output is correct
3 Correct 1580 ms 174428 KB Output is correct
4 Correct 1780 ms 171228 KB Output is correct
5 Correct 950 ms 162312 KB Output is correct
6 Correct 912 ms 162236 KB Output is correct
7 Correct 1364 ms 162220 KB Output is correct
8 Correct 929 ms 162512 KB Output is correct
9 Correct 1079 ms 164980 KB Output is correct
10 Correct 874 ms 162164 KB Output is correct
11 Correct 677 ms 161996 KB Output is correct
12 Correct 674 ms 162264 KB Output is correct
13 Incorrect 1444 ms 163708 KB Output isn't correct
14 Halted 0 ms 0 KB -