Submission #93498

#	Time	Username	Problem	Language	Result	Execution time	Memory
93498		tincamatei	Teams (IOI15_teams)	C++14	0 / 100	713 ms	21880 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

const int MAX_N = 500000;
const int BUCK = 707;
//const int MAX_N = 10;
//const int BUCK = 2;
const int NB = MAX_N / BUCK + 1;

int n, a[MAX_N], b[MAX_N];
int fr[NB+1][NB];
int goright[1+MAX_N], goleft[1+MAX_N];
int del[NB];

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

  for(int i = 0; i < n; ++i) {
    a[i] = A[i];
    b[i] = B[i];
    fr[a[i] / BUCK + 1][b[i] / BUCK]++;
    fr[b[i] / BUCK + 1][b[i] / BUCK]--;
    //printf("%d %d %d %d %d %d\n", a[i], b[i], a[i] / BUCK + 1, b[i] / BUCK + 1, b[i] / BUCK, BUCK);

    goright[a[i]]++;
    goleft[b[i]]++;
  }

  for(int i = 1; i <= NB; ++i)
    for(int j = 0; j < NB; ++j)
      fr[i][j] += fr[i - 1][j];
}

int can(int M, int K[]) {
  for(int i = 0; i < NB; ++i)
    del[i] = 0;

  sort(K, K + M);

  int i = 0;
  while(i < M) {
    int b = K[i] / BUCK;
    int lb = b * BUCK, rb = lb + BUCK -  1;

    int added = fr[b][b];

    for(int poz = lb; poz <= rb; ++poz) {
      added += goright[poz];
      while(i < M && K[i] == poz) {
        // Process Query
        if(added - del[b] < K[i]) {
          K[i] -= added - del[b];
          del[b] = added;
        } else {
          del[b] += K[i];
          K[i] = 0;
        }

        int j = b + 1;
        while(j < NB && K[i] > 0) {
          if(fr[b][j] - del[j] < K[i]) {
            K[i] -= fr[b][j] - del[j];
            del[j] = fr[b][j];
          } else {
            del[j] += K[i];
            K[i] = 0;
          }
          ++j;
        }

        if(K[i] > 0)
          return false;

        ++i;
      }

      if(goleft[poz] <= del[b])
        del[b] -= goleft[poz];
      else {
        added = added - (goleft[poz] - del[b]);
        del[b] = 0;
      }

      if(added < 0) return false;
    }
  }

  return true;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:44:9: warning: declaration of 'b' shadows a global declaration [-Wshadow]
     int b = K[i] / BUCK;
         ^
teams.cpp:12:18: note: shadowed declaration is here
 int n, a[MAX_N], b[MAX_N];
                  ^

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