Submission #987165

#	Time	Username	Problem	Language	Result	Execution time	Memory
987165		huutuan	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	14 ms	3160 KiB

elephants

#include "elephants.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=2e5+10, inf=1e9, S=450;
int n, m, len, a[N];
pair<int, int> pos[N];
vector<pair<int, int>> vv;
int cnt_query;

struct Block{
   vector<int> v, nxt, jump, cnt;
   int lazy, id;
   Block(){ lazy=-1; id=0; }
   void push(){
      if (lazy!=-1){
         for (int i=0; i<(int)v.size(); ++i){
            nxt[i]=lazy;
            jump[i]=lazy;
            cnt[i]=1;
         }
      }
   }
   void calc(){
      for (int i=0; i<(int)v.size(); ++i) pos[v[i]]={id, i};
      for (int i=(int)v.size()-1; i>=0; --i){
         if (pos[nxt[i]].first!=id){
            jump[i]=nxt[i];
            cnt[i]=1;
         }else{
            jump[i]=jump[pos[nxt[i]].second];
            cnt[i]=cnt[pos[nxt[i]].second]+1;
         }
      }
   }
   int get_nxt(int i){
      if (lazy==-1) return nxt[i];
      return lazy;
   }
} bl[S+10];

void build(bool p){
   vector<pair<int, int>> v;
   if (!p){
      v.emplace_back(n, n);
      for (int i=n-1, j=n; i>=0; --i){
         while (vv[j-1].first-vv[i].first>len) --j;
         v.emplace_back(i, j);
      }
      reverse(v.begin(), v.end());
   }else{
      for (int i=0; i<=m; ++i){
         bl[i].push();
         for (int j=0; j<(int)bl[i].v.size(); ++j) v.emplace_back(bl[i].v[j], bl[i].nxt[j]);
         bl[i].v.clear();
         bl[i].nxt.clear();
         bl[i].jump.clear();
         bl[i].cnt.clear();
      }
   }
   m=0;
   for (int i=0; i<=n; ++i){
      if ((int)bl[m].v.size()==S || i==n) ++m;
      bl[m].id=m;
      pos[v[i].first]={m, bl[m].v.size()};
      bl[m].v.push_back(v[i].first);
      bl[m].nxt.push_back(v[i].second);
      bl[m].jump.push_back(0);
      bl[m].cnt.push_back(0);
   }
   bl[m].jump[0]=n;
   for (int i=0; i<m; ++i){
      bl[i].calc();
   }
}

void update(int l, int r, int val){
   if (pos[l].first==pos[r].first){
      int id=pos[l].first;
      bl[id].push();
      for (int i=pos[l].second; i<=pos[r].second; ++i){
         bl[id].nxt[i]=val;
      }
      bl[id].calc();
      return;
   }
   {
      int id=pos[l].first;
      bl[id].push();
      for (int i=pos[l].second; i<(int)bl[id].v.size(); ++i) bl[id].nxt[i]=val;
      bl[id].calc();
   }
   {
      int id=pos[r].first;
      bl[id].push();
      for (int i=0; i<pos[r].second; ++i) bl[id].nxt[i]=val;
      bl[id].calc();
   }
   for (int i=pos[l].first+1; i<pos[r].first; ++i) bl[i].lazy=val;
}

int get(){
   pair<int, int> p={0, 0};
   int ans=0;
   while (p.first!=m){
      if (bl[p.first].lazy==-1){
         ans+=bl[p.first].cnt[p.second];
         p=pos[bl[p.first].jump[p.second]];
      }else{
         ++ans;
         p=pos[bl[p.first].lazy];
      }
   }
   return ans;
}

void init(int32_t _N, int32_t L, int32_t X[])
{
   n=_N;
   len=L;
   for (int i=0; i<n; ++i) a[i]=X[i];
   a[n]=inf;
   for (int i=0; i<n; ++i) vv.emplace_back(a[i], i);
   sort(vv.begin(), vv.end());
   build(0);
}

int32_t update(int32_t _i, int32_t _y)
{
   ++cnt_query;
   if (cnt_query%400==0){
      build(1);
   }
   int i=_i, y=_y;
   int tl=-1, tr=-1, tt=-1;
   {
      int id=m;
      while (id>=0){
         if (pos[bl[id].get_nxt(0)]>pos[i]) --id;
         else{
            for (int j=(int)bl[id].v.size()-1; j>=0; --j){
               if (pos[bl[id].get_nxt(j)]<=pos[i]){
                  tr=bl[id].v[j];
                  break;
               }
            }
            break;
         }
      }
   }
   {
      int id=0;
      while (1){
         if (pos[bl[id].get_nxt((int)bl[id].v.size()-1)]<pos[i]) ++id;
         else{
            for (int j=0; j<(int)bl[id].v.size(); ++j){
               if (pos[bl[id].get_nxt(j)]>=pos[i]){
                  tl=bl[id].v[j];
                  break;
               }
            }
            break;
         }
      }
   }
   {
      pair<int, int> p=pos[i];
      ++p.second;
      if (p.second>=(int)bl[p.first].v.size()) ++p.first, p.second=0;
      tt=bl[p.first].v[p.second];
   }
   if (tl!=-1 && tr!=-1 && pos[tl]<=pos[tr]){
      update(tl, tr, tt);
   }
   bl[pos[i].first].v.erase(bl[pos[i].first].v.begin()+pos[i].second);
   bl[pos[i].first].nxt.erase(bl[pos[i].first].nxt.begin()+pos[i].second);
   bl[pos[i].first].jump.erase(bl[pos[i].first].jump.begin()+pos[i].second);
   bl[pos[i].first].cnt.erase(bl[pos[i].first].cnt.begin()+pos[i].second);
   pair<int, int> p={-1, -1}, p2={-1, -1};
   {
      a[i]=y;
      int id=m-1;
      while (1){
         if (id && make_pair(a[bl[id].v[0]], bl[id].v[0])>make_pair(a[i], i)) --id;
         else{
            p={id, 0};
            for (int j=0; j<(int)bl[id].v.size(); ++j){
               if (make_pair(a[bl[id].v[j]], bl[id].v[j])<=make_pair(a[i], i)){
                  p={id, j+1};
               }
            }
            break;
         }
      }
   }
   bl[p.first].push();
   bl[p.first].v.insert(bl[p.first].v.begin()+p.second, i);
   {
      int id=0;
      while (1){
         if (make_pair(a[bl[id].v.back()], bl[id].v.back())<make_pair(a[i]+len, inf)) ++id;
         else{
            for (int j=0; j<(int)bl[id].v.size(); ++j){
               if (make_pair(a[bl[id].v[j]], bl[id].v[j])>=make_pair(a[i]+len, inf)){
                  p2={id, j};
                  break;
               }
            }
            break;
         }
      }
   }
   bl[p.first].nxt.insert(bl[p.first].nxt.begin()+p.second, bl[p2.first].v[p2.second]);
   bl[p.first].jump.insert(bl[p.first].jump.begin()+p.second, 0);
   bl[p.first].cnt.insert(bl[p.first].cnt.begin()+p.second, 0);
   bl[p.first].calc();
   p2=p;
   ++p2.second;
   if (p2.second==(int)bl[p2.first].v.size()) ++p2.first, p2.second=0;
   {
      tl=-1, tr=-1, tt=-1;
      {
         int id=m;
         while (id>=0){
            if (pos[bl[id].get_nxt(0)]>p2 || a[bl[id].v[0]]+len>=y) --id;
            else{
               for (int j=(int)bl[id].v.size()-1; j>=0; --j){
                  if (pos[bl[id].get_nxt(j)]<=p2 && a[bl[id].v[j]]+len<y){
                     tr=bl[id].v[j];
                     break;
                  }
               }
               break;
            }
         }
      }
      {
         int id=0;
         while (1){
            if (pos[bl[id].get_nxt((int)bl[id].v.size()-1)]<p2) ++id;
            else{
               for (int j=0; j<(int)bl[id].v.size(); ++j){
                  if (pos[bl[id].get_nxt(j)]>=p2){
                     tl=bl[id].v[j];
                     break;
                  }
               }
               break;
            }
         }
      }
      if (tl!=-1 && tr!=-1 && pos[tl]<=pos[tr]){
         update(tl, tr, i);
      }
   }
   return get();
}

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