Submission #1240219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240219		simplemind_31	Dancing Elephants (IOI11_elephants)	C++20	26 / 100	9091 ms	4932 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
int n,l;
vector<int> ele;
set<int> cont;
set<int> cam;
void init(int N,int L,int X[]){
  ele.resize(n=N);
  l=L;
  for(int i=0;i<n;i++){
    cont.insert(ele[i]=X[i]);
  }
  cam.insert(-l-1);
  for(int i=0;i<n;i++){
    if(L+*(--cam.end())<ele[i]){
      cam.insert(ele[i]);
    }
  }
}
int update(int i,int y){
  auto p=--cam.upper_bound(ele[i]);
  if(*p==ele[i]){
    cont.erase(ele[i]);
    cam.erase(p);
    auto q=cont.upper_bound(ele[i]);
    if(q!=cont.end()){
      int nextnum=*q;
      while(*(--cam.upper_bound(nextnum))+l<nextnum){
        cam.insert(nextnum);
        auto p=cam.upper_bound(nextnum);
          if(p!=cam.end()){
          if(nextnum+l>=*p){
            cam.erase(p);
            auto q=cont.upper_bound(nextnum+l);
            if(q!=cont.end()){
              nextnum=*q;
            }
          }
        }
      }
    }
    ele[i]=y;
    cont.insert(ele[i]);
    int nextnum=ele[i];
    //auto p=--cam.upper_bound(ele[i]);
    while(*(--cam.upper_bound(nextnum))+l<nextnum){
      cam.insert(nextnum);
      auto p=cam.upper_bound(nextnum);
      if(p!=cam.end()){
        if(nextnum+l>=*p){
          cam.erase(p);
          auto q=cont.upper_bound(nextnum+l);
          if(q!=cont.end()){
            nextnum=*q;
          }
        }
      }
    }
  }else{
    cont.erase(ele[i]);
    ele[i]=y;
    cont.insert(ele[i]);
    int nextnum=ele[i];
    //auto p=--cam.upper_bound(ele[i]);
    while(*(--cam.upper_bound(nextnum))+l<nextnum){
      cam.insert(nextnum);
      auto p=cam.upper_bound(nextnum);
      if(p!=cam.end()){
        if(nextnum+l>=*p){
          cam.erase(p);
          auto q=cont.upper_bound(nextnum+l);
          if(q!=cont.end()){
            nextnum=*q;
          }
        }
      }
    }
  }
  return cam.size()-1;
}

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