Submission #117516

#	Time	Username	Problem	Language	Result	Execution time	Memory
117516		zubec	Teams (IOI15_teams)	C++14	100 / 100	2493 ms	363192 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 500100;

vector <int> t, L, R;

int nleaf(int x){
    t.push_back(x);
    L.push_back(-1);
    R.push_back(-1);
    return t.size()-1;
}

int vcopy(int l, int r){
    t.push_back(t[l]+t[r]);
    L.push_back(l);
    R.push_back(r);
    return t.size()-1;
}

int build(int l = 0, int r = N-1){
    if (l == r)
        return nleaf(0);
    int mid = (l+r)>>1;
    return vcopy(build(l, mid), build(mid+1, r));
}

int rem(int v1, int v2, int x, int l = 0, int r = N-1){
    if (r <= x)
        return v2;
    if (l > x)
        return v1;
    int mid = (l+r)>>1;
    return vcopy(rem(L[v1], L[v2], x, l, mid), rem(R[v1], R[v2], x, mid+1, r));
}

int update(int v, int x, int l = 0, int r = N-1){
    if (l == r){
        return nleaf(t[v] + 1);
    }
    int mid = (l+r)>>1;
    if (x <= mid)
        return vcopy(update(L[v], x, l, mid), R[v]); else
        return vcopy(L[v], update(R[v], x, mid+1, r));
}

int update2(int v1, int v2, int x, int l = 0, int r = N-1){
    if (l == r){
        return nleaf(t[v1]+x);
    }
    int mid = (l+r)>>1;
    int kol = t[L[v2]]-t[L[v1]];
    if (kol >= x)
        return vcopy(update2(L[v1], L[v2], x, l, mid), R[v1]);
        return vcopy(L[v2], update2(R[v1], R[v2], x-kol, mid+1, r));
}

int n, root[N];

vector <int> g[N];

int empt;

void init(int N, int A[], int B[]) {
    n = N;
    root[0] = build();
    for (int i = 0; i < n; i++){
        g[A[i]].push_back(B[i]);
    }
    for (int i = 1; i <= n; i++){
        root[i] = rem(root[i-1], root[0], i-1);
        for (int j = 0; j < g[i].size(); j++){
            root[i] = update(root[i], g[i][j]);
        }
    }
    empt = build();
}

int can(int M, int K[]) {
    int cur = empt;
    sort(K, K+M);
    for (int i = 0; i < M; i++){
        cur = rem(cur, root[0], K[i]-1);
        if (t[root[K[i]]]-t[cur] < K[i])
            return 0;
        cur = update2(cur, root[K[i]], K[i]);
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int nleaf(int)':
teams.cpp:14:20: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     return t.size()-1;
            ~~~~~~~~^~
teams.cpp: In function 'int vcopy(int, int)':
teams.cpp:21:20: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     return t.size()-1;
            ~~~~~~~~^~
teams.cpp: In function 'int update2(int, int, int, int, int)':
teams.cpp:56:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (kol >= x)
     ^~
teams.cpp:58:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         return vcopy(L[v2], update2(R[v1], R[v2], x-kol, mid+1, r));
         ^~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:67:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 void init(int N, int A[], int B[]) {
                                  ^
teams.cpp:6:11: note: shadowed declaration is here
 const int N = 500100;
           ^
teams.cpp:75:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[i].size(); j++){
                         ~~^~~~~~~~~~~~~

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