Submission #121033

#	Time	Username	Problem	Language	Result	Execution time	Memory
121033		RockyB	Teams (IOI15_teams)	C++17	77 / 100	4107 ms	277476 KiB

teams

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include"teams.h"

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)5e5 + 5;
const int MAXP = (int)2e7 + 5;

struct Node {
    int c1, c2, sum;

    Node(int x = 0) {
        c1 = c2 = -1;
        sum = x;
    }
} pers[MAXP];

vector<int> V[MAXN];

int W[1005][1005];

int root[MAXN];

int cnt[MAXN];

pii arr[MAXN];

ll dp[1005];

int n, sz;

int newleaf(int x) {
    pers[sz].sum = x;
    pers[sz].c1 = 0;
    pers[sz].c2 = 0;
    return sz++;    
}

int newpar(int a, int b) {
    pers[sz].c1 = a;
    pers[sz].c2 = b;
    pers[sz].sum = pers[a].sum + pers[b].sum;
    return sz++;
}

int updVal(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        return newleaf(pers[v].sum + 1);
    }

    int mid = (tl + tr) >> 1;

    if (pos <= mid) {
        return newpar(updVal(pers[v].c1, tl, mid, pos), pers[v].c2);
    }
    else {
        return newpar(pers[v].c1, updVal(pers[v].c2, mid + 1, tr, pos));
    }
}

int segSum(int v, int tl, int tr, int l, int r) {
    if (v == 0 || l > r || tl > r || tr < l) {
        return 0;
    }

    if (l <= tl && tr <= r) {
        return pers[v].sum;        
    }

    int mid = (tl + tr) >> 1;

    return segSum(pers[v].c1, tl, mid, l, r)
    + segSum(pers[v].c2, mid + 1, tr, l, r);
}

void init(int N, int A[], int B[]) {
    root[0] = newpar(0, 0);
    n = N;

    for (int i = 1; i <= n; ++i) {
        arr[i] = mp(A[i - 1], B[i - 1]);
        V[arr[i].fi].pb(arr[i].se);
    }

    for (int i = 1; i <= n; ++i) {
        root[i] = root[i - 1];

        for (int pos : V[i]) {
            root[i] = updVal(root[i], 1, n, pos);
        }
    }                                                                                                                            
}

int can(int m, int sz[]) {
    vector<int> V;
    int sum = 0;

    for (int i = 0; i < m; ++i) {
        sum += sz[i];

        if (sum > n) {
            return 0;
        }
    }    
    
    for (int i = 0; i < m; ++i) {
        if (cnt[sz[i]]++ == 0) {
            V.pb(sz[i]);
        }
    }

    sort(all(V));

    // l <= x <= r
    // l <= y <= r

    for (int i = 0; i < V.size(); ++i) {
        for (int j = i; j < V.size(); ++j) {
            W[i][j] = segSum(root[V[i]], 1, n, V[j], n);                         
        }
    }

    for (int i = 0; i < V.size(); ++i) {
        dp[i] = 0;

        for (int j = 0; j < i; ++j) {
            dp[i] = max(dp[i], dp[j] + W[j][i]);
        } 

        dp[i] += V[i] * 1ll * cnt[V[i]] - W[i][i];
    }    

    for (int i = 0; i < m; ++i) {
        --cnt[sz[i]];
    }

    return *max_element(dp, dp + V.size()) <= 0;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:115:24: warning: declaration of 'sz' shadows a global declaration [-Wshadow]
 int can(int m, int sz[]) {
                        ^
teams.cpp:51:8: note: shadowed declaration is here
 int n, sz;
        ^~
teams.cpp:116:17: warning: declaration of 'V' shadows a global declaration [-Wshadow]
     vector<int> V;
                 ^
teams.cpp:39:13: note: shadowed declaration is here
 vector<int> V[MAXN];
             ^
teams.cpp:138:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < V.size(); ++i) {
                     ~~^~~~~~~~~~
teams.cpp:139:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i; j < V.size(); ++j) {
                         ~~^~~~~~~~~~
teams.cpp:144:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < V.size(); ++i) {
                     ~~^~~~~~~~~~

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