Submission #766522

#	Time	Username	Problem	Language	Result	Execution time	Memory
766522		lukameladze	Teams (IOI15_teams)	C++17	100 / 100	3891 ms	174700 KiB

teams

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

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