oj.uz

Submission #99597

# Submission time Handle Problem Language Result Execution time Memory
99597 2019-03-05T14:04:42 Z eriksuenderhauf Teams (IOI15_teams) C++11
100 / 100
 2526 ms 174352 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));
    	if (curCnt > n)
        	return 0;
      	while (d.size() > 1 && gt(d[d.size()-2], d.back()) <= gt(d.back(), i))
        	d.pop_back();
        d.pb(i);
    }
    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
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 49940 KB Output is correct
2 Correct 152 ms 50008 KB Output is correct
3 Correct 157 ms 49912 KB Output is correct
4 Correct 156 ms 51064 KB Output is correct
5 Correct 77 ms 48780 KB Output is correct
6 Correct 66 ms 48900 KB Output is correct
7 Correct 74 ms 48860 KB Output is correct
8 Correct 81 ms 48888 KB Output is correct
9 Correct 390 ms 49668 KB Output is correct
10 Correct 207 ms 49392 KB Output is correct
11 Correct 72 ms 49136 KB Output is correct
12 Correct 73 ms 49096 KB Output is correct
13 Correct 72 ms 49268 KB Output is correct
14 Correct 88 ms 49520 KB Output is correct
15 Correct 125 ms 49912 KB Output is correct
16 Correct 130 ms 49984 KB Output is correct
17 Correct 75 ms 49204 KB Output is correct
18 Correct 68 ms 49252 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 50268 KB Output is correct
2 Correct 166 ms 50424 KB Output is correct
3 Correct 335 ms 53368 KB Output is correct
4 Correct 138 ms 51064 KB Output is correct
5 Correct 266 ms 49208 KB Output is correct
6 Correct 312 ms 49220 KB Output is correct
7 Correct 91 ms 49220 KB Output is correct
8 Correct 220 ms 49232 KB Output is correct
9 Correct 349 ms 49792 KB Output is correct
10 Correct 897 ms 49868 KB Output is correct
11 Correct 686 ms 49520 KB Output is correct
12 Correct 544 ms 49584 KB Output is correct
13 Correct 540 ms 49900 KB Output is correct
14 Correct 486 ms 52104 KB Output is correct
15 Correct 307 ms 50668 KB Output is correct
16 Correct 281 ms 50808 KB Output is correct
17 Correct 271 ms 49656 KB Output is correct
18 Correct 278 ms 49780 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1065 ms 168596 KB Output is correct
2 Correct 998 ms 168476 KB Output is correct
3 Correct 1669 ms 174352 KB Output is correct
4 Correct 982 ms 169588 KB Output is correct
5 Correct 928 ms 162252 KB Output is correct
6 Correct 983 ms 162208 KB Output is correct
7 Correct 250 ms 162296 KB Output is correct
8 Correct 778 ms 162424 KB Output is correct
9 Correct 2526 ms 164156 KB Output is correct
10 Correct 2268 ms 161972 KB Output is correct
11 Correct 1763 ms 161992 KB Output is correct
12 Correct 1378 ms 162008 KB Output is correct
13 Correct 2225 ms 163604 KB Output is correct
14 Correct 1869 ms 170644 KB Output is correct
15 Correct 1061 ms 167432 KB Output is correct
16 Correct 1196 ms 167456 KB Output is correct
17 Correct 868 ms 162448 KB Output is correct
18 Correct 788 ms 162444 KB Output is correct