oj.uz

Submission #766522

# Submission time Handle Problem Language Result Execution time Memory
766522 2023-06-25T18:27:52 Z lukameladze Teams (IOI15_teams) C++17
100 / 100
 3891 ms 174700 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 5e5 + 5;
int n,m,tree[30 * N], le_[30 * N], ri_[30 * N], cur, k[N], dp[N],a[N],b[N],root[N];
vector <int> v[N];
set <int> s1;
set <pii> s;
int merge(int a, int b) {
    return a + b;
}
void build(int node, int le, int ri) {
    if (le == ri) {
        return ;
    }
    le_[node] = ++cur;
    ri_[node] = ++cur;
    int mid = (le + ri) / 2;
    build(le_[node], le, mid);
    build(ri_[node], mid + 1, ri);
    tree[node] = merge(tree[le_[node]], tree[ri_[node]]);
}
void update(int node, int le, int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        tree[cur] = tree[node] + val;
        return ;
    }
    int mid = (le + ri) / 2;

    int vert = cur;

    le_[cur] = le_[node];
    ri_[cur] = ri_[node];
    if (idx <= mid) {
        le_[vert] = ++cur;
    }
    else {
        ri_[vert] = ++cur;
    }
    update(le_[node], le, mid, idx, val);
    update(ri_[node], mid + 1, ri, idx, val);
    tree[vert] = merge(tree[le_[vert]], tree[ri_[vert]]);
}
int getans(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return 0;
    if (le >= start && ri <= end) return tree[node];
    int mid = (le + ri) / 2;
    return merge(getans(le_[node], le, mid, start, end), getans(ri_[node], mid + 1, ri, start, end));
}
void init(int N, int A[], int B[]) {
    n = N;
    for (int i = 1; i <= n; i++) {
        a[i] = A[i - 1]; b[i] = B[i - 1];
        v[a[i]].pb(b[i]);
    }
    root[0] = 1; cur = 1;
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        root[i] = root[i - 1];
        for (int x : v[i]) {
            int pr_root = root[i];
            root[i] = ++cur;
            update(pr_root, 1, n, x, 1);
        }
    }
}
int get(int i, int j) {
    int le = k[j] + 1, ri = n, ans = 0;
    while (le <= ri) {
        int mid = (le + ri) / 2;
        if (dp[i] + (getans(root[k[j]], 1,n, mid, n) - getans(root[k[i]],1,n, mid, n)) < dp[j]) {
            ans = mid; ri = mid - 1;
        } else le = mid + 1;
    }
    return ans;
}
void del(int idx) {
    if (!s1.count(idx)) return ;
    s1.erase(idx);
    auto it = s1.upper_bound(idx);
    int nxt = (it == s1.end() ? -1 : *it);
    int pre = (it == s1.begin() ? -1 : *(--it));
    if (pre != -1) {
        if (get(pre, idx)) s.erase({get(pre, idx), idx});
    }
    if (nxt != -1) {
        if (get(idx, nxt)) s.erase({get(idx, nxt), nxt});
    }
    if (pre != -1 && nxt != -1) {
        if (get(pre, nxt)) s.insert({get(pre, nxt), nxt});
    }
}
void add(int idx) {
    if (s1.count(idx)) return ;
    if (!s1.size()) { s1.insert(idx); return ; }
    auto it = s1.upper_bound(idx);
    int nxt = (it == s1.end() ? -1 : *it);
    int pre = (it == s1.begin() ? -1 : *(--it));
    if (pre != -1 && nxt != -1) {
        if (get(pre, nxt)) s.erase({get(pre, nxt), nxt});
    }
    if (pre != -1) if(get(pre, idx)) s.insert({get(pre, idx), idx});
    if (nxt != -1) if (get(idx, nxt)) s.insert({get(idx, nxt), nxt});
    s1.insert(idx);
}
int can(int M, int K[]) {
    s.clear(); s1.clear();
    m = M;
    for (int i = 1; i <= m; i++) {
        k[i] = K[i - 1]; dp[i] = 0;
    }
    sort(k + 1, k + m + 1);
    add(0);
    for (int i = 1; i <= m; i++) {
        while (s.size() && (*s.begin()).f <= k[i]) {
            del((*s.begin()).s);
        }
        int id = (*--s1.end());
        dp[i] = dp[id] + getans(root[k[i]], 1, n, k[i], n) - getans(root[k[id]], 1, n, k[i], n) - k[i];
        if (dp[i] < 0) {
            return 0;
        }
        add(i);
    }
	return 1;
}

Compilation message

teams.cpp: In function 'int merge(int, int)':
teams.cpp:14:22: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   14 | int merge(int a, int b) {
      |                  ~~~~^
teams.cpp:10:71: note: shadowed declaration is here
   10 | int n,m,tree[30 * N], le_[30 * N], ri_[30 * N], cur, k[N], dp[N],a[N],b[N],root[N];
      |                                                                       ^
teams.cpp:14:15: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   14 | int merge(int a, int b) {
      |           ~~~~^
teams.cpp:10:66: note: shadowed declaration is here
   10 | int n,m,tree[30 * N], le_[30 * N], ri_[30 * N], cur, k[N], dp[N],a[N],b[N],root[N];
      |                                                                  ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:56:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   56 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:9:11: note: shadowed declaration is here
    9 | const int N = 5e5 + 5;
      |           ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 12048 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 6 ms 12116 KB Output is correct
5 Correct 6 ms 12052 KB Output is correct
6 Correct 6 ms 12140 KB Output is correct
7 Correct 6 ms 12052 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12096 KB Output is correct
10 Correct 6 ms 12112 KB Output is correct
11 Correct 6 ms 12048 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 8 ms 12048 KB Output is correct
15 Correct 6 ms 12116 KB Output is correct
16 Correct 6 ms 12116 KB Output is correct
17 Correct 6 ms 12052 KB Output is correct
18 Correct 6 ms 12116 KB Output is correct
19 Correct 9 ms 12172 KB Output is correct
20 Correct 6 ms 12056 KB Output is correct
21 Correct 6 ms 12052 KB Output is correct
22 Correct 5 ms 12116 KB Output is correct
23 Correct 6 ms 12048 KB Output is correct
24 Correct 6 ms 12116 KB Output is correct
25 Correct 5 ms 11988 KB Output is correct
26 Correct 5 ms 12116 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 40068 KB Output is correct
2 Correct 51 ms 40100 KB Output is correct
3 Correct 52 ms 40120 KB Output is correct
4 Correct 67 ms 41424 KB Output is correct
5 Correct 32 ms 38760 KB Output is correct
6 Correct 31 ms 38584 KB Output is correct
7 Correct 31 ms 38552 KB Output is correct
8 Correct 30 ms 38652 KB Output is correct
9 Correct 121 ms 39544 KB Output is correct
10 Correct 72 ms 38328 KB Output is correct
11 Correct 34 ms 38680 KB Output is correct
12 Correct 30 ms 37444 KB Output is correct
13 Correct 35 ms 39168 KB Output is correct
14 Correct 40 ms 38560 KB Output is correct
15 Correct 49 ms 39820 KB Output is correct
16 Correct 48 ms 39860 KB Output is correct
17 Correct 34 ms 39088 KB Output is correct
18 Correct 34 ms 39200 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 40824 KB Output is correct
2 Correct 60 ms 40816 KB Output is correct
3 Correct 482 ms 44160 KB Output is correct
4 Correct 55 ms 41368 KB Output is correct
5 Correct 306 ms 39300 KB Output is correct
6 Correct 260 ms 39316 KB Output is correct
7 Correct 36 ms 39324 KB Output is correct
8 Correct 205 ms 39356 KB Output is correct
9 Correct 118 ms 39492 KB Output is correct
10 Correct 266 ms 38736 KB Output is correct
11 Correct 287 ms 39244 KB Output is correct
12 Correct 351 ms 38260 KB Output is correct
13 Correct 771 ms 40116 KB Output is correct
14 Correct 814 ms 42288 KB Output is correct
15 Correct 702 ms 40764 KB Output is correct
16 Correct 702 ms 40784 KB Output is correct
17 Correct 667 ms 39876 KB Output is correct
18 Correct 758 ms 39952 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 167888 KB Output is correct
2 Correct 461 ms 167960 KB Output is correct
3 Correct 2453 ms 174700 KB Output is correct
4 Correct 484 ms 168980 KB Output is correct
5 Correct 808 ms 159160 KB Output is correct
6 Correct 736 ms 159332 KB Output is correct
7 Correct 144 ms 159232 KB Output is correct
8 Correct 601 ms 159104 KB Output is correct
9 Correct 632 ms 161552 KB Output is correct
10 Correct 761 ms 157720 KB Output is correct
11 Correct 787 ms 157688 KB Output is correct
12 Correct 991 ms 158520 KB Output is correct
13 Correct 2671 ms 161700 KB Output is correct
14 Correct 3891 ms 169356 KB Output is correct
15 Correct 2098 ms 166252 KB Output is correct
16 Correct 2041 ms 166272 KB Output is correct
17 Correct 1940 ms 160796 KB Output is correct
18 Correct 1938 ms 160804 KB Output is correct