oj.uz

Submission #385004

# Submission time Handle Problem Language Result Execution time Memory
385004 2021-04-02T22:04:58 Z thiago4532 Teams (IOI15_teams) C++17
77 / 100
 4000 ms 339756 KB 
#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

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
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 59116 KB Output is correct
2 Correct 156 ms 59628 KB Output is correct
3 Correct 146 ms 59628 KB Output is correct
4 Correct 164 ms 60912 KB Output is correct
5 Correct 125 ms 59392 KB Output is correct
6 Correct 112 ms 59268 KB Output is correct
7 Correct 116 ms 59372 KB Output is correct
8 Correct 107 ms 59244 KB Output is correct
9 Correct 97 ms 57856 KB Output is correct
10 Correct 98 ms 57068 KB Output is correct
11 Correct 116 ms 60140 KB Output is correct
12 Correct 107 ms 57068 KB Output is correct
13 Correct 113 ms 60268 KB Output is correct
14 Correct 111 ms 58092 KB Output is correct
15 Correct 140 ms 59620 KB Output is correct
16 Correct 135 ms 59628 KB Output is correct
17 Correct 120 ms 60524 KB Output is correct
18 Correct 129 ms 60524 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 59756 KB Output is correct
2 Correct 151 ms 60396 KB Output is correct
3 Correct 264 ms 64204 KB Output is correct
4 Correct 149 ms 60912 KB Output is correct
5 Correct 3995 ms 60196 KB Output is correct
6 Correct 2800 ms 60296 KB Output is correct
7 Correct 115 ms 60012 KB Output is correct
8 Correct 2147 ms 60040 KB Output is correct
9 Correct 95 ms 57708 KB Output is correct
10 Correct 105 ms 57548 KB Output is correct
11 Correct 161 ms 60752 KB Output is correct
12 Correct 1686 ms 58164 KB Output is correct
13 Correct 468 ms 61292 KB Output is correct
14 Correct 303 ms 62316 KB Output is correct
15 Correct 210 ms 60584 KB Output is correct
16 Correct 210 ms 60524 KB Output is correct
17 Correct 236 ms 61328 KB Output is correct
18 Correct 205 ms 61332 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 327404 KB Output is correct
2 Correct 925 ms 331860 KB Output is correct
3 Correct 1320 ms 339756 KB Output is correct
4 Correct 916 ms 334312 KB Output is correct
5 Execution timed out 4116 ms 330688 KB Time limit exceeded
6 Halted 0 ms 0 KB -