oj.uz

Submission #987169

# Submission time Handle Problem Language Result Execution time Memory
987169 2024-05-22T07:50:11 Z huutuan Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 8588 KB 
#include "elephants.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=2e5+10, inf=1e9, S=450, S2=400;
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[N/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%S2==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);
   bl[pos[i].first].calc();
   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 (id && (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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 420 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 420 KB Output is correct
7 Correct 379 ms 3480 KB Output is correct
8 Correct 416 ms 4488 KB Output is correct
9 Correct 622 ms 8588 KB Output is correct
10 Correct 411 ms 8256 KB Output is correct
11 Execution timed out 9098 ms 8000 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 420 KB Output is correct
7 Correct 379 ms 3480 KB Output is correct
8 Correct 416 ms 4488 KB Output is correct
9 Correct 622 ms 8588 KB Output is correct
10 Correct 411 ms 8256 KB Output is correct
11 Execution timed out 9098 ms 8000 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 420 KB Output is correct
7 Correct 379 ms 3480 KB Output is correct
8 Correct 416 ms 4488 KB Output is correct
9 Correct 622 ms 8588 KB Output is correct
10 Correct 411 ms 8256 KB Output is correct
11 Execution timed out 9098 ms 8000 KB Time limit exceeded
12 Halted 0 ms 0 KB -