Submission #63303

#	Time	Username	Problem	Language	Result	Execution time	Memory
63303		evpipis	Jousting tournament (IOI12_tournament)	C++11	100 / 100	181 ms	26352 KiB

tournament

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

//#define TEST

#ifdef TEST
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
#endif // TEST

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

const int len = 2e5+5;
vector<int> adj[len];
int nex[len], nod[len], fir[len], tree[2*len];
ii inter[len];

void update(int p, int l, int r, int i, int v){
    if (l == r)
        tree[p] += v;
    else{
        int mid = (l+r)/2;
        if (i <= mid)
            update(2*p, l, mid, i, v);
        else
            update(2*p+1, mid+1, r, i, v);

        tree[p] = tree[2*p] + tree[2*p+1];
    }
}

int query(int p, int l, int r, int k){
    //printf("(l, r) = (%d, %d), k = %d\n", l, r, k);
    if (l == r)
        return l;

    int mid = (l+r)/2;
    if (k <= tree[2*p])
        return query(2*p, l, mid, k);
    return query(2*p+1, mid+1, r, k-tree[2*p]);
}

ii dfs(int u){
    if (adj[u].size() == 0) return mp(0, u);

    ii ans = mp(-1, -1);
    int temp = (fir[inter[u].fi] >= inter[u].se);
    for (int j = 0; j < adj[u].size(); j++){
        int v = adj[u][j];
        //out[v] = out[u]+temp;
        ii cur = dfs(v);

        if (cur.fi > ans.fi)
            ans = cur;
        else if (cur.fi == ans.fi && cur.se < ans.se)
            ans = cur;
    }

    ans.fi += temp;
    return ans;
}

int GetBestPosition(int n, int q, int p, int *arr, int *st, int *en){
    int m = n-1;
    for (int i = 0; i < n; i++){
        nex[i] = i+1;
        nod[i] = i;
    }

    for (int i = 0; i < n; i++)
        update(1, 0, n-1, i, 1);

    for (int i = 0; i < q; i++){
        int beg = query(1, 0, n-1, st[i]+1), pos = beg, rem = en[i]-st[i];

        ++m;
        update(1, 0, n-1, beg, 1);
        while (rem--){
            update(1, 0, n-1, pos, -1);
            adj[m].pb(nod[pos]);
            pos = nex[pos];
        }
        adj[m].pb(nod[pos]);
        update(1, 0, n-1, pos, -1);


        nex[beg] = nex[pos];
        nod[beg] = m;
        inter[m] = mp(beg, nex[beg]-1);

        //printf("beg = %d, end = %d\n", beg, nex[beg]-1);
    }

    /*for (int i = 0; i <= m; i++){
        printf("%d(%d, %d):", i, inter[i].fi, inter[i].se);
        for (int j = 0; j < adj[i].size(); j++)
            printf(" %d", adj[i][j]);
        printf("\n");
    }*/

    arr[n-1] = n;
    for (int i = 0, j = 0; i < n; i++){
        j = max(j, i);
        while (arr[j] <= p)
            j++;

        fir[i] = j;
        //printf("i = %d, j = %d\n", i, j);
    }

    //printf("%d, %d\n", dfs(m).fi, dfs(m).se);
    /*ii temp = dfs(m);
    ii ans = mp(-1, -1);
    for (int i = 0; i < n; i++)
        if (out[i] > ans.fi || (out[i] == ans.fi && i < ans.se))
            ans = mp(out[i], i);*/

    //for (int i = 0; i < n; i++)
      //  printf("%d ", out[i]);
    //printf("\n");
    return dfs(m).se;
}

#ifdef TEST
int main() {
  //freopen("example.txt", "r", stdin);
  int tmp;

  /* Set input and output buffering */
  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, C, R;
  int *K, *S, *E;
  tmp = scanf("%d %d %d", &N, &C, &R);
  assert(tmp == 3);
  K = (int*) malloc((N-1) * sizeof(int));
  S = (int*) malloc(C * sizeof(int));
  E = (int*) malloc(C * sizeof(int));
  int i;
  for (i = 0; i < N-1; i++) {
    tmp = scanf("%d", &K[i]);
    assert(tmp == 1);
  }
  for (i = 0; i < C; i++) {
    tmp = scanf("%d %d", &S[i], &E[i]);
    assert(tmp == 2);
  }

  printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  return 0;

}
#endif // TEST

/*
8 5 3
0 1 2 4 5 6 7
1 3
2 3
3 4
0 2
0 1

5 4 2
0 1 3 4
0 1
0 1
0 1
0 1
*/

Compilation message (stderr)

tournament.cpp: In function 'ii dfs(int)':
tournament.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51