oj.uz

Submission #987172

# Submission time Handle Problem Language Result Execution time Memory
987172 2024-05-22T08:06:09 Z huutuan Dancing Elephants (IOI11_elephants) C++14
97 / 100
 4479 ms 33060 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;
         }
         lazy=-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;
   // cout << cnt_query << endl;
   // cout << bl[155].nxt[0] << endl;
   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();
   if (bl[m-1].v.empty()){
      bl[m-1]=bl[m];
      --bl[m-1].id;
      pos[n]={m-1, 0};
      --m;
   }
   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 344 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 344 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 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 396 ms 3792 KB Output is correct
8 Correct 421 ms 4356 KB Output is correct
9 Correct 590 ms 8636 KB Output is correct
10 Correct 406 ms 8224 KB Output is correct
11 Correct 352 ms 8232 KB Output is correct
12 Correct 694 ms 8552 KB Output is correct
13 Correct 404 ms 8068 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 396 ms 3792 KB Output is correct
8 Correct 421 ms 4356 KB Output is correct
9 Correct 590 ms 8636 KB Output is correct
10 Correct 406 ms 8224 KB Output is correct
11 Correct 352 ms 8232 KB Output is correct
12 Correct 694 ms 8552 KB Output is correct
13 Correct 404 ms 8068 KB Output is correct
14 Correct 545 ms 5424 KB Output is correct
15 Correct 613 ms 5584 KB Output is correct
16 Correct 869 ms 9080 KB Output is correct
17 Correct 1146 ms 12252 KB Output is correct
18 Correct 1111 ms 12232 KB Output is correct
19 Correct 905 ms 12448 KB Output is correct
20 Correct 1103 ms 12384 KB Output is correct
21 Correct 1202 ms 12196 KB Output is correct
22 Correct 867 ms 11744 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 396 ms 3792 KB Output is correct
8 Correct 421 ms 4356 KB Output is correct
9 Correct 590 ms 8636 KB Output is correct
10 Correct 406 ms 8224 KB Output is correct
11 Correct 352 ms 8232 KB Output is correct
12 Correct 694 ms 8552 KB Output is correct
13 Correct 404 ms 8068 KB Output is correct
14 Correct 545 ms 5424 KB Output is correct
15 Correct 613 ms 5584 KB Output is correct
16 Correct 869 ms 9080 KB Output is correct
17 Correct 1146 ms 12252 KB Output is correct
18 Correct 1111 ms 12232 KB Output is correct
19 Correct 905 ms 12448 KB Output is correct
20 Correct 1103 ms 12384 KB Output is correct
21 Correct 1202 ms 12196 KB Output is correct
22 Correct 867 ms 11744 KB Output is correct
23 Correct 4479 ms 26060 KB Output is correct
24 Correct 4257 ms 25884 KB Output is correct
25 Correct 3983 ms 25636 KB Output is correct
26 Correct 3662 ms 25924 KB Output is correct
27 Correct 4273 ms 26156 KB Output is correct
28 Correct 1034 ms 6024 KB Output is correct
29 Correct 1034 ms 5980 KB Output is correct
30 Correct 1100 ms 6168 KB Output is correct
31 Correct 1020 ms 6100 KB Output is correct
32 Correct 3208 ms 25220 KB Output is correct
33 Correct 3096 ms 24628 KB Output is correct
34 Correct 3745 ms 25532 KB Output is correct
35 Runtime error 74 ms 33060 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -