Submission #385013

#	Time	Username	Problem	Language	Result	Execution time	Memory
385013		thiago4532	Teams (IOI15_teams)	C++17	0 / 100	122 ms	16812 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;

const int maxnos = 1e7 + 10;

struct node {
    int l, r;
    int v;
    node () {
        l = r = 0;
        v = 0;
    }
};
vector<node> id;

inline int l(int t) {
    return t ? id[t].l : 0;
}

inline int r(int t) {
    return t ? id[t].r : 0;
}

inline int valor(int t) {
    return t ? id[t].v : 0;
}

inline int lastpos(vector<node> const& vetor) {
    return (int)vetor.size() - 1;
}

void build(int& no, int ini = 1, int fim = n) {
    id.push_back(node()), no = lastpos(id);
    if (ini == fim) return;

    int meio = (ini + fim) / 2;
    build(id[no].l, ini, meio);
    build(id[no].r, meio+1, fim);
}

void update(int old, int no, int p, int v, int ini=1, int fim=n) {
    if (ini == fim) {
        id[no].v = valor(old) + v;
        return;
    }

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

    if (p <= meio) {
        if (l(old) == 0) id.push_back(node()), id[no].l = lastpos(id);
        else id.push_back(node( id[l(old)] )), id[no].l = lastpos(id);

        if(r(old)) id[no].r = id[old].r;

        update(l(old), id[no].l, p, v, ini, meio);
    }else {
        if (r(old) == 0) id.push_back(node()), id[no].r = lastpos(id);
        else id.push_back(node( id[r(old)] )), id[no].r = lastpos(id);

        if(l(old)) id[no].l = id[old].l;

        update(r(old), id[no].r, p, v, meio+1, fim);
    }

    id[no].v = valor(id[no].l) + valor(id[no].r);
}

int query(int no, int l, int r, int ini=1, int fim=n) {
    if(no == 0 || ini > r || fim < l) return 0;
    if(l <= ini && fim <= r) return id[no].v;

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

    int p1 = query(id[no].l, l, r, ini, meio);
    int p2 = query(id[no].r, l, r, meio+1, fim);
    return p1 + p2;
}
int 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 no;
    build(no);
    int last = 0;
    for (int i = 1; i <= n; i++) {
        if (v[i].ff != last) {
            ver[last] = nv;
            last = v[i].ff;
        }

        id.push_back(node());
        version[++nv] = lastpos(id);
        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(int, int, int, int, int, int)':
teams.cpp:55:64: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   55 | void update(int old, int 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