Submission #93482

#	Time	Username	Problem	Language	Result	Execution time	Memory
93482		tincamatei	Teams (IOI15_teams)	C++14	0 / 100	4014 ms	70140 KiB

teams

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

using namespace std;

const int MAX_N = 500000;

int n;
int a[MAX_N], b[1+MAX_N];
int poz[1+MAX_N];

vector<int> goright[1+MAX_N];
vector<int> goleft[1+MAX_N];

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

  for(int i = 0; i < n; ++i) {
    poz[i] = i;
    a[i] = A[i];
    b[i] = B[i];
  }
  for(int i = 0; i < N; ++i) {
    goright[a[i]].push_back(i);
    goleft[b[i]].push_back(i);
  }
}

int can(int M, int K[]) {
  set<pair<int, int> > xd;

  std::sort(K, K + M);

  int lastup = 0;
  for(int i = 1; i <= n; ++i) {
    for(int j = 0; j < goright[i].size(); ++j) {
      int it = goright[i][j];
      xd.insert(make_pair(b[it], it));
    }

    while(lastup < M && K[lastup] == i) {
      for(int j = 0; j < i; ++j) {
        if(xd.empty())
          return false;
        xd.erase(xd.begin());
      }
      ++lastup;
    }

    for(int j = 0; j < goleft[i].size(); ++j) {
      int it = goleft[i][j];
      xd.erase(make_pair(i, it));
    }
  }

	return lastup < M;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < goright[i].size(); ++j) {
                    ~~^~~~~~~~~~~~~~~~~~~
teams.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < goleft[i].size(); ++j) {
                    ~~^~~~~~~~~~~~~~~~~~

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