Submission #135733

#	Time	Username	Problem	Language	Result	Execution time	Memory
135733		evpipis	Teams (IOI15_teams)	C++11	100 / 100	1544 ms	349788 KiB

teams

//#define TEST

#ifndef TEST
#include "teams.h"
#endif // TEST

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 5e5+5;
vector<int> stud[len];
int team[len], n, dp[len], pre[len], nex[len], in[len];
priority_queue<ii, vector<ii>, greater<ii> > pq;

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);
}

int query(pnode a, pnode b, int l, int r, int x){
    //printf("l = %d, r = %d, x = %d\n", l, r, x);
    if (l == r){
        if ((a->sum-b->sum) <= x)
            return l;
        return l+1;
    }

    int mid = (l+r)/2, rig = (a->right->sum-b->right->sum);
    if (rig <= x)
        return query(a->left, b->left, l, mid, x-rig);
    return query(a->right, b->right, mid+1, r, x);
}

void init(int N, int A[], int B[]){
    n = N;
    for (int i = 1; i <= n; i++)
        stud[i].clear();
    for (int i = 0; i < n; i++)
        stud[A[i]].pb(B[i]);

    //for (int i = 0; i < n; i++)
      //  printf("student: %d - %d\n", A[i], 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[]){
    for (int i = 1; i <= m; i++)
        team[i] = K[i-1];
    sort(team+1, team+m+1);

    int sum = 0;
    for (int i = 1; i <= m; i++)
        sum = min(n+1, team[i]+sum);

    if (sum > n)
        return 0;

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

    while (!pq.empty())
        pq.pop();
    for (int i = 0; i <= m; i++){
        in[i] = 0;
        pre[i] = -1;
        nex[i] = -1;
    }
    in[0] = 1, pre[0] = -1, nex[0] = -1;

    int ans = 1, opt = 0;
    for (int i = 1; i <= m; i++){
        while (!pq.empty() && pq.top().fi <= team[i]){
            ii cur = pq.top();
            pq.pop();

            if (!in[cur.se]) continue;
            in[cur.se] = 0;

            int pr = pre[cur.se], ne = nex[cur.se];
            nex[pr] = ne;
            if (ne == -1){
                opt = pr;
            }
            else{
                pre[ne] = pr;
                //printf("%d with %d: %d\n", pr, ne, query(root[team[ne]], root[team[pr]], 1, n, dp[ne]-dp[pr]));
                pq.push(mp(query(root[team[ne]], root[team[pr]], 1, n, dp[ne]-dp[pr]), ne));
            }
        }

        int tim = query(root[team[i-1]], root[team[opt]], 1, n, dp[i-1]-dp[opt]);
        //printf("%d with %d: %d\n", opt, i-1, tim);
        if (i != 1 && tim > team[i]){
            in[i-1] = 1;
            nex[opt] = i-1;
            pre[i-1] = opt;
            nex[i-1] = -1;
            opt = i-1;
            pq.push(mp(tim, opt));
        }

        //printf("i = %d, team = %d, opt = %d\n", i, team[i], opt);

        dp[i] = dp[opt]+ask(root[team[i]], root[team[opt]], 1, n, team[i], n)-team[i];

        //printf("i = %d, dp = %d\n", i, dp[i]);

        //printf("i = %d, opt = %d, dp = %d\n", i, opt, dp[i]);
        /*printf("all opts:");
        for (int j = opt; j != -1; j = pre[j])
            printf(" %d", j);
        printf("\n");*/
        if (dp[i] < 0)
            ans = 0;
    }
    //printf("ans = %d\n", ans);
	return ans;
}

#ifdef TEST

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}

int main() {
    for (int t = 1; t <= 30; t++){
        char test[10];
        if (t < 10)
            sprintf(test, "0%d", t);
        else
            sprintf(test, "%d", t);

        printf("test file %s\n", test);

        _inputFile = fopen(test, "rb");

        //_outputFile = fopen("teams2.out", "w");
        int N;
        N = _readInt();
        int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
        int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
        for (int i = 0; i < N; ++i) {
            A[i] = _readInt();
            B[i] = _readInt();
        }

        if (N <= 1000)
            init(N, A, B);

        printf("N = %d\n", N);

        //vector<int> hel;
        //hel.clear();

        int Q;
        Q = _readInt();
        //Q = 1;
        printf("Q = %d\n", Q);
        for (int i = 0; i < Q; ++i) {
            //printf("quere number %d\n", i);
            int M;
            M = _readInt();
            //printf("M = %d\n", M);
        int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
            for (int j = 0; j < M; ++j) {
                K[j] = _readInt();
            }

            /*printf("M = %d\n", M);
            for (int j = 0; j < M; j++)
                printf("%d ", K[j]);
            printf("\n");*/

            if (N <= 1000){
                //hel.pb(can(M, K));
                fprintf(_outputFile,"%d\n", can(M, K));
            }
        }

        /*if (0){
            if (t < 10)
                sprintf(test, "0%d.a", t);
            else
                sprintf(test, "%d.a", t);
            _inputFile = fopen(test, "rb");

            for (int i = 0; i < Q; i++){
                int cor = _readInt();
                if (cor != hel[i])
                    printf("my answer = %d, correct = %d\n", hel[i], cor);
            }
        }*/
    }
    return 0;
}
#endif // TEST

Compilation message (stderr)

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

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