Submission #135079

#	Time	Username	Problem	Language	Result	Execution time	Memory
135079		evpipis	Teams (IOI15_teams)	C++11	0 / 100	1451 ms	350072 KiB

teams

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

#define pb push_back
const int len = 5e5+5;
vector<int> stud[len];
int team[len], n, pref[len], extra[len], every[len];

struct node{
    int sum;
    node *left, *right;

    node(int s = 0, node *l = NULL, node *r = NULL){
        sum = s;
        left = l;
        right = r;
    }
};

typedef node* pnode;
pnode null = new node(), root[len];

pnode update(pnode t, int l, int r, int i){
    if (l == r)
        return new node(t->sum+1, null, null);

    int mid = (l+r)/2;
    if (i <= mid)
        return new node(t->sum+1, update(t->left, l, mid, i), t->right);
    return new node(t->sum+1, t->left, update(t->right, mid+1, r, i));
}

int ask(pnode a, pnode b, int l, int r, int i, int j){
    if (r < i || j < l || i > j)
        return 0;
    if (i <= l && r <= j)
        return (a->sum-b->sum);

    int mid = (l+r)/2;
    return ask(a->left, b->left, l, mid, i, j) + ask(a->right, b->right, mid+1, r, i, j);
}

void init(int N, int A[], int B[]){
    //freopen("CON", "w", stdout);

    n = N;
    for (int i = 0; i < n; i++)
        stud[A[i]].pb(B[i]);

    root[0] = null->left = null->right = null;
    for (int i = 1; i <= n; i++){
        root[i] = root[i-1];
        for (int j = 0; j < stud[i].size(); j++)
            root[i] = update(root[i], 1, n, stud[i][j]);
    }
}

int can(int m, int K[]){
    //freopen("CON", "w", stdout);

    for (int i = 1; i <= m; i++)
        team[i] = K[i-1];
    sort(team+1, team+m+1);

    /*printf("team =\n");
    for (int i = 1; i <= m; i++)
        printf("%d ", team[i]);
    printf("\n");*/

    for (int i = 1; i <= m; i++){
        pref[i] = min(n+1, pref[i-1]+team[i]);
        extra[i] = extra[i-1]+ask(root[team[i]], root[team[i-1]], 1, n, team[i], n);
        every[i] = ask(root[team[i]], root[team[0]], 1, n, team[i], n);

        //printf("i = %d, pref = %d, extra = %d, every = %d\n", i, pref[i], extra[i], every[i]);
    }

    int ans = 1, mn = 0;
    for (int i = m; i >= 1; i--){
        mn = min(mn, extra[i]-pref[i]);
        //printf("i = %d, mn = %d\n", i, mn);
        //printf("i = %d, cur = %d\n", i, every[i]-extra[i]+pref[i-1] + mn);
        if (every[i]-extra[i]+pref[i-1] + mn < 0)
            ans = 0;
    }

    //printf("ans = %d\n", ans);
	return ans;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:54:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < stud[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~~

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