oj.uz

Submission #99607

# Submission time Handle Problem Language Result Execution time Memory
99607 2019-03-05T14:56:35 Z eriksuenderhauf Teams (IOI15_teams) C++11
0 / 100
 1494 ms 280952 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;
}

int xy[MAXN][2];
void init(int n, int a[], int b[]) {
    ::n = n;
    for (int i = 0; i < n; i++)
        arr[a[i] - 1].pb(b[i]), xy[i][0] = a[i], xy[i][1] = 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) >= dp[y] + qry(0, n+1, root[pos[y]], 0, pos[mi] - 1))
            hi = mi;
        else
            lo = mi + 1;
    }
    
    for (int i = y; i <= m + 1; i++)
        if (dp[x] + qry(0, n+1, root[pos[x]], 0, pos[i] - 1) >= dp[y] + qry(0, n+1, root[pos[y]], 0, pos[i] - 1)) {
            int c = 0;
            for (int j = 0; j < n; j++)
                if (xy[j][0] <= pos[y] && pos[y] <= xy[j][1] && xy[j][1] < pos[j])
                    c++;
            int l = (dp[x] + qry(0, n+1, root[pos[x]], 0, pos[i] - 1)) - (dp[y] + qry(0, n+1, root[pos[y]], 0, pos[i] - 1));
            if (c != l)
                exit(-1);
            return i;
        }
    return m+2;
}

int can(int m, int k[]) {
    ::m = m;
    pos = {0};
    vi tmp;
    for (int i = 0; i < m; i++) {
        pos.pb(k[i]);
        tmp.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:62: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:98: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 25 ms 23808 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 26 ms 23936 KB Output is correct
4 Correct 26 ms 23952 KB Output is correct
5 Correct 27 ms 23928 KB Output is correct
6 Correct 26 ms 24064 KB Output is correct
7 Runtime error 27 ms 24064 KB Execution failed because the return code was nonzero
8 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 50780 KB Output is correct
2 Correct 129 ms 50680 KB Output is correct
3 Correct 134 ms 50780 KB Output is correct
4 Correct 164 ms 52244 KB Output is correct
5 Runtime error 150 ms 89816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 51216 KB Output is correct
2 Correct 269 ms 51236 KB Output is correct
3 Correct 326 ms 54264 KB Output is correct
4 Correct 164 ms 52084 KB Output is correct
5 Runtime error 149 ms 89796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 172640 KB Output is correct
2 Correct 1207 ms 172424 KB Output is correct
3 Correct 1494 ms 178296 KB Output is correct
4 Correct 1226 ms 174276 KB Output is correct
5 Runtime error 459 ms 280952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -