Submission #1241179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241179		porquenomedejainiciarsesion	코끼리 (Dancing Elephants) (IOI11_elephants)	C++20	26 / 100	9089 ms	2772 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
int n,l;
multiset<int> S;
set<int> Starts;
unordered_map<int,int> starts2;
unordered_map<int,int> M;
vector<int> A;
void init(int N, int L, int X[])
{
  for(int i=0;i<N;i++){
    M[X[i]]++;
    S.insert(X[i]);
    A.push_back(X[i]);
  }
  l=L;
  n = N;
}
int updates=0;
int ans;
int update(int i, int y)
{
  updates++;
  int old=A[i];
  A[i]=y;
  auto it=S.find(old); 
  if (it!=S.end()) S.erase(it);
  S.insert(y);
  bool ok=false;
  if (starts2[old]==1) {
    ok=true;
  }
  bool ok2 = false;
  if (!Starts.empty()) {
    auto it=Starts.upper_bound(y);
    if (it!=Starts.begin()) {
      --it;
      if (*it+l>=y) {
        ok2=true;
      }
    }
  }
  if(updates==1 || ok || !ok2){
    ans=0;
    int last = -1e9;
    starts2.clear();
    Starts.clear();
    for (auto x:S) {
      if (last + l < x) {
        last = x;
        starts2[last] = 1;
        Starts.insert(last);
        ans++;
      }
    }
  }
  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3