Submission #987122

#	Time	Username	Problem	Language	Result	Execution time	Memory
987122		huutuan	Dancing Elephants (IOI11_elephants)	C++14	10 / 100	3 ms	10596 KiB

elephants

#include "elephants.h"

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

#define int long long

template<class T>
using ordered_set=
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct Node{
   int lazy;
   Node *tl, *tr;
   Node (){
      lazy=-1;
      tl=nullptr;
      tr=nullptr;
   }
   void apply(int x){
      lazy=x;
   }
   void push(){
      if (lazy!=-1){
         tl->apply(lazy);
         tr->apply(lazy);
         lazy=-1;
      }
   }
   void operator~(){
      if (tl!=nullptr){
         delete tl;
         delete tr;
      }
      delete this;
   }
};

struct SegmentTree{
   Node *root;
   void update(Node *t, int l, int r, int L, int R, int val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         t->apply(val);
         return;
      }
      if (t->tl==nullptr){
         t->tl=new Node();
         t->tr=new Node();
      }
      t->push();
      int mid=(l+r)>>1;
      update(t->tl, l, mid, L, R, val);
      update(t->tr, mid+1, r, L, R, val);
   }
   int get(Node *t, int l, int r, int pos){
      if (l==r) return t->lazy;
      t->push();
      int mid=(l+r)>>1;
      if (pos<=mid) return get(t->tl, l, mid, pos);
      return get(t->tr, mid+1, r, pos);
   }
} seg;

const int N=2e5+10, inf=1e9;
int n, len, pos[N], nxt[N], dist[N];
ordered_set<pair<int, int>> st;

void init(int32_t _N, int32_t L, int32_t X[])
{
   n = _N, len=L;
   seg.root=new Node();
   for (int i=0; i<n; ++i) pos[i]=X[i];
   vector<pair<int, int>> v;
   for (int i=0; i<n; ++i) v.emplace_back(pos[i], i);
   pos[n]=inf;
   v.emplace_back(inf, n);
   sort(v.begin(), v.end());
   for (int i=0, j=0; i<n; ++i){
      while (j<n && v[j].first-v[i].first<=len) ++j;
      nxt[v[i].second]=(j==n?n:v[j].second);
   }
   dist[n]=0;
   for (int i=n-1; i>=0; --i) dist[v[i].second]=dist[nxt[v[i].second]]+1;
   for (int i=0; i<=n; ++i) seg.update(seg.root, 0, 1e18, pos[i]*(n+1)+i, pos[i]*(n+1)+i, dist[i]);
   for (auto &i:v) st.insert(i);
}

int32_t update(int32_t _i, int32_t _y)
{
   int i=_i;
   auto it=st.find({pos[i], i});
   int id=st.order_of_key({pos[i], i});
   {
      int pl, pr;
      {
         int l=0, r=n-1;
         while (l<=r){
            int mid=(l+r)>>1;
            auto it2=st.find_by_order(mid);
            int id2=st.order_of_key({it2->first+len, inf});
            if (id2>id) r=mid-1;
            else l=mid+1;
         }
         pr=r;
      }
      {
         int l=0, r=n-1;
         while (l<=r){
            int mid=(l+r)>>1;
            auto it2=st.find_by_order(mid);
            int id2=st.order_of_key({it2->first+len, inf});
            if (id2>=id) r=mid-1;
            else l=mid+1;
         }
         pl=l;
      }
      int d=seg.get(seg.root, 0, 1e18, pos[next(it)->second]*(n+1)+next(it)->second);
      if (pl<=pr){
         auto itl=st.find_by_order(pl), itr=st.find_by_order(pr);
         seg.update(seg.root, 0, 1e18, itl->first*(n+1)+itl->second, itr->first*(n+1)+itr->second, d+1);
      }
   }
   st.erase(it);
   pos[i]=_y;
   st.insert({pos[i], i});
   it=st.find({pos[i], i});
   id=st.order_of_key(*it);
   auto tmp=st.upper_bound({pos[i]+len, inf});
   dist[i]=seg.get(seg.root, 0, 1e18, pos[tmp->second]*(n+1)+tmp->second)+1;
   seg.update(seg.root, 0, 1e18, pos[i]*(n+1)+i, pos[i]*(n+1)+i, dist[i]);
   {
      int pl, pr;
      {
         int l=0, r=n-1;
         while (l<=r){
            int mid=(l+r)>>1;
            auto it2=st.find_by_order(mid);
            int id2=st.order_of_key({it2->first+len, inf});
            if (id2>id) r=mid-1;
            else l=mid+1;
         }
         pr=r;
      }
      {
         int l=0, r=n-1;
         while (l<=r){
            int mid=(l+r)>>1;
            auto it2=st.find_by_order(mid);
            int id2=st.order_of_key({it2->first+len, inf});
            if (id2>=id) r=mid-1;
            else l=mid+1;
         }
         pl=l;
      }
      if (pl<=pr){
         auto itl=st.find_by_order(pl), itr=st.find_by_order(pr);
         seg.update(seg.root, 0, 1e18, itl->first*(n+1)+itl->second, itr->first*(n+1)+itr->second, dist[i]+1);
      }
   }
   return seg.get(seg.root, 0, 1e18, st.begin()->first*(n+1)+st.begin()->second);
}

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