Submission #1044844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044844		NeroZein	Teams (IOI15_teams)	C++17	34 / 100	4024 ms	25428 KiB

teams

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

const int N = 1e5 + 5; 

int n;
int a[N], b[N];
vector<int> qa[N], qr[N];

void init(int n_, int a_[], int b_[]) {
  n = n_;
  for (int i = 0; i < n; ++i) {
    a[i] = a_[i];
  }
  for (int i = 0; i < n; ++i) {
    b[i] = b_[i];
  }
  for (int i = 0; i < n; ++i) {
    qa[a[i]].push_back(i);
    qr[b[i]].push_back(i);     
  }
}

int can(int m, int k[]) {
  sort(k, k + m); 
  set<pair<int, int>> se; 
  for (int i = 1, p = 0; i <= n; ++i) {
    for (int j : qa[i]) {
      se.insert({b[j], j});        
    }
    while (p < m && k[p] == i) {
      if ((int) se.size() < i) {
        return 0; 
      }
      for (int j = 0; j < k[p]; ++j) {
        se.erase(se.begin()); 
      }
      p++; 
    }
    for (int j : qr[i]) {
      if (se.count({b[j], j})) {
        se.erase({b[j], j}); 
      }
    }
  }
  return 1;
}

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