Submission #385003

#	Time	Username	Problem	Language	Result	Execution time	Memory
385003		thiago4532	Teams (IOI15_teams)	C++17	0 / 100	1058 ms	335432 KiB

teams

#define _FORTIFY_SOURCE 0 
#pragma GCC optimize("Ofast") 
#pragma GCC optimize("no-stack-protector") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("avx,avx2,fma") 
#include "teams.h"
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef pair<int, int> pii;
const int maxn = 5e5 + 10;
const int maxq = 2e5 + 10;
pii v[maxn];
int n;

struct node {
    node *l, *r;
    int v;
    node () {
        l = r = nullptr;
        v = 0;
    }
};

inline int val(node *t) {
    if (t != nullptr) return t->v;
    return 0;
}

inline node* l(node* t) {
    return t ? t->l : nullptr;
}

inline node* r(node *t ) {
    return t ? t->r : nullptr;
}

inline int valor(node *t) {
    return t ? t->v : 0;
}

void update(node *old, node *no, int p, int v, int ini=1, int fim=n) {
    if (ini == fim) {
        no->v = valor(old) + v;
        return;
    }

    int meio = (ini + fim) >> 1;

    if (p <= meio) {
        if (old == nullptr || old->l == nullptr) no->l = new node;
        else no->l = new node(*old->l);

        if(old != nullptr && old->r != nullptr) no->r = old->r;

        update(l(old), no->l, p, v, ini, meio);
    }else {
        if (old == nullptr || old->r == nullptr) no->r = new node;
        else no->r = new node(*old->r);

        if(old != nullptr && old->l != nullptr) no->l = old->l;

        update(r(old), no->r, p, v, meio+1, fim);
    }

    no->v = val(no->l) + val(no->r);
}

int query(node *no, int l, int r, int ini=1, int fim=n) {
    if(no == nullptr || ini > r || fim < l) return 0;
    if(l <= ini && fim <= r) return no->v;

    int meio = (ini + fim) >> 1;

    int p1 = query(no->l, l, r, ini, meio);
    int p2 = query(no->r, l, r, meio+1, fim);
    return p1 + p2;
}
node* version[maxn];
int nv, ver[maxn];

void init(int N, int A[], int B[]) {
    n = N;
    for (int i = 1; i <= n; i++)
        v[i] = {A[i-1], B[i-1]};

    sort(v+1, v+n+1);

    int last = 0;
    for (int i = 1; i <= n; i++) {
        if (v[i].ff != last) {
            ver[last] = nv;
            last = v[i].ff;
        }

        version[++nv] = new node;
        update(version[nv-1], version[nv], v[i].ss, 1);
    }
    ver[last] = nv;
    for (int i = 1; i <= n; i++)
        ver[i] = max(ver[i-1], ver[i]);
    //cout << "OI " << nv << '\n';
    for (int i = 1; i <= n; i++)
        cout << ver[i] << " \n"[i==nv];
}
int qtd[maxn];
typedef long long ll;
ll dp[maxn];
int freq[maxn];

inline ll solve(int l, int r, int ini, int fim) {
    return query(version[ ver[r] ], ini, fim) - (l>0?query(version[ ver[l] ], ini, fim):0);
}

int can(int M, int K[]) {
    vector<int> q;
    ll sum = 0;
    for (int i = 0; i < M; i++) 
        q.push_back(K[i]), sum += K[i];
    if (sum > n) return 0;
    for (auto& e : q)
        freq[e]++;

    sort(q.begin(), q.end());
    q.erase(unique(q.begin(), q.end()), q.end());

    bool certo = true;
    int m = (int)q.size(); // m < sqrt(M)
    for (int i = 0; i < m; i++) {
        ll f = 1ll*freq[q[i]]*q[i]; // numero de caras na esquerda
        dp[i] = solve(0, q[i], q[i], n) - f;

        for (int j = 0; j < i; j++)
            dp[i] = min(dp[i], dp[j] + solve(q[j], q[i], q[i], n) - f);

        if (dp[i] < 0) { // vizinhanca menor que 0
            certo = false;
            break;
        }
    }

    for (int i = 0; i < m; i++)
        dp[i] = 0;
    for (auto& e : q)
        freq[e] = 0;

    return certo;
}

// matching perfeito ( teorema de hall )
// S(vizinhanca de A) >= S(A) para todo o subset

Compilation message (stderr)

teams.cpp:1: warning: "_FORTIFY_SOURCE" redefined
    1 | #define _FORTIFY_SOURCE 0
      | 
<built-in>: note: this is the location of the previous definition
teams.cpp: In function 'void update(node*, node*, int, int, int, int)':
teams.cpp:44:68: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   44 | void update(node *old, node *no, int p, int v, int ini=1, int fim=n) {
      |                                                                    ^
teams.cpp:15:5: note: shadowed declaration is here
   15 | pii v[maxn];
      |     ^

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23