Submission #99598

#	Time	Username	Problem	Language	Result	Execution time	Memory
99598		eriksuenderhauf	Teams (IOI15_teams)	C++11	100 / 100	1742 ms	174328 KiB

teams

#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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23