Submission #911248

#	Time	Username	Problem	Language	Result	Execution time	Memory
911248		cadmiumsky	Fish 2 (JOI22_fish2)	C++17	100 / 100	3357 ms	54368 KiB

fish2

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
 
using ll = long long;
using ld = long double;
 
//#define int ll
#define sz(x) ((int)(x).size())
 
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
 
const int nmax = 1e5 + 5;
const int inf = 1e9 + 5;
 
template<typename Node> 
struct AINT {
  vector<Node> aint;
  int n;
  void init(int _n, Node TMP = Node()) {
    n = _n;
    aint.assign(2 * n + 5, TMP);
  }
  
  tii getsons(int node, int cl, int cr) { int mid = cl + cr >> 1; return tii{mid, node + 1, node + (mid - cl + 1) * 2};}
  
  template<class CB> void walk(int ismutable, int toRight, CB&& cb) { 
    if(ismutable == 0 && toRight == 0) walk<0, 0>(cb, 1, 1, n); 
    else if(ismutable == 0) walk<0, 1>(cb, 1, 1, n); 
    else if(toRight == 0) walk<1, 0>(cb, 1, 1, n);
    else walk<1, 1>(cb, 1, 1, n);
  }
  template<int ismutable, int toRight, class CB> void walk(CB&& cb, int node, int cl, int cr) { 
    
    //cerr << node << '\t' << cl << ' ' << cr << '\n';
    
    if(!cb(aint[node], cl, cr)) return;
    
    auto [mid, L, R] = getsons(node, cl, cr);
    aint[node].push(aint[L], aint[R]);
    
    if(toRight) walk<ismutable, toRight>(cb, L, cl, mid), walk<ismutable, toRight>(cb, R, mid + 1, cr);
    else walk<ismutable, toRight>(cb, R, mid + 1, cr), walk<ismutable, toRight>(cb, L, cl, mid);
    
    if(ismutable) aint[node].pull(aint[L], aint[R]);
    return;
  }
};
 
struct MinCounter {
  int mn, cnt;
  
  int add;
  
  MinCounter(int a, int b, int c = 0): mn(a), cnt(b), add(c) {;}
  MinCounter(): mn(inf), cnt(0), add(0) {;}
  
  void push(MinCounter& a, MinCounter& b) {
    a.mn += add;
    a.add += add;
    b.add += add;
    b.mn += add;
    
    add = 0;
  }
  
  void pull(const MinCounter a, const MinCounter b) {
    *this = MinCounter(min(a.mn, b.mn), a.cnt * (a.mn <= b.mn) + b.cnt * (b.mn <= a.mn));
  }
};
 
struct GreaterFinder {
  int mx;
  GreaterFinder(int a = 0): mx(a) {;}
  void pull(const GreaterFinder& a, const GreaterFinder& b) { *this = GreaterFinder(max(a.mx, b.mx)); }
  void push(const GreaterFinder& a, const GreaterFinder& b) {;}
};
 
struct Sum {
  ll sum;
  Sum(ll a = 0): sum(a) {;}
  void pull(const Sum& a, const Sum& b) { *this = Sum(a.sum + b.sum); }
  void push(const Sum& a, const Sum& b) {;}
};
 
int a[nmax];
 
AINT<Sum> sum;
 
ll getsum(int l, int r) { 
  ll rez = 0;
  
  //for(int i = l; i <= r; i++)
    //rez += a[i];
  
  sum.walk(0, 1, [&](Sum& a, int cl, int cr) { if(cr < l || r < cl) return 0; if(l <= cl && cr <= r) { rez += a.sum; return 0; } return 1; }); return rez; 
  
  return rez;
}
 
AINT<MinCounter> mncnt;
 
int n;
 
namespace Finders {
  AINT<GreaterFinder> finder;
  
  int nextGreater(int P, ll lim) { // urmatorul de la pozitia P >= lim
    int rez = n + 1;
    finder.walk(0, 1, 
      [&](GreaterFinder& a, int cl, int cr) { if(rez < cl) return 0; if(cr < P || a.mx < lim) { rez = cr + 1; return 0; } if(cl == cr) { rez = cl; return 0; } return 1; });
    return rez;
  }
  
  int prevGreater(int P, ll lim) {
    int rez = 0;
    finder.walk(0, 0, 
      [&](GreaterFinder& a, int cl, int cr) { if(rez > cr) return 0; if(P < cl || a.mx < lim) { rez = cl - 1; return 0; } if(cl == cr) { rez = cl; return 0; } return 1; });
    return rez;
  }
  
  int nextBreaker(int L, int start) {
    int ptr = start;
    while(ptr < n) {
      int essai = nextGreater(ptr + 1, getsum(L, ptr) + 1);
      if(essai == ptr + 1) {
        return ptr + 1;
      }
      ptr = essai - 1;
    }
    return n + 1;
  }
  
  int prevBreaker(int R, int start) {
    int ptr = start;
    while(ptr > 1) {
      int essai = prevGreater(ptr - 1, getsum(ptr, R) + 1);
      if(essai == ptr - 1) {
        return ptr - 1;
      }
      ptr = essai + 1;
    }
    return 0;
  }
}
 
 
vector<pii> getIntervs(int P) {
  
  using namespace Finders;
  vector<pii> elems;
  
  
  
  int L = P, R = P, direction = 1, fail = 0;
  while(L > 1 || R < n) {
    if(direction == 1) {
      int nvR = nextBreaker(L, R) - 1;
      if(nvR == R && fail) {
        elems.emplace_back(L, R);
        if((L != 1 && a[L - 1] <= a[R + 1]) || R == n) L--;
        else R++;
        fail = 0;
      }
      else { fail = R == nvR; R = nvR; }
    }
    
    else {
      int nvL = prevBreaker(R, L) + 1;
      if(nvL == L && fail) {
        elems.emplace_back(L, R);
        if((L != 1 && a[L - 1] <= a[R + 1]) || R == n) L--;
        else R++;
        fail = 0;
      }
      else {fail = L == nvL; L = nvL; }
    }
    
    direction *= -1;
  }
  
  return elems;
}
 
 
namespace Segments {
  unordered_set<int> rightends[nmax];
  unordered_set<int> leftends[nmax];
  
  void erase(int l, int r) {
    if(leftends[l].count(r)) {
      leftends[l].erase(r);
      rightends[r].erase(l);
      
      mncnt.walk(1, 1, [&](MinCounter& val, int cl, int cr) {
        if(cr < l || r < cl) return 0;
        if(l <= cl && cr <= r) {
          val.mn -= 1;
          val.add -= 1;
          return 0;
        }
        return 1;
      });
    }
    return;
  }
  
  void insert(int l, int r) {
    if(!leftends[l].count(r)) {
      leftends[l].insert(r);
      rightends[r].insert(l);
      
      mncnt.walk(1, 1, [&](MinCounter& val, int cl, int cr) {
        if(cr < l || r < cl) return 0;
        if(l <= cl && cr <= r) {
          val.mn += 1;
          val.add += 1;
          return 0;
        }
        return 1;
      });
    }
    return;
  }
}
 
void updPoz(int P, int x) {
  
  vector<pii> V = getIntervs(P), T;
  V.reserve(60);
  if(P > 1) for(auto x : Segments::rightends[P - 1]) V.emplace_back(x, P - 1);
  if(P < n) for(auto x : Segments::leftends[P + 1]) V.emplace_back(P + 1, x);
  
  for(auto [l, r] : V)
    Segments::erase(l, r);
  
  Finders::finder.walk(1, 1, [&](GreaterFinder& val, int cl, int cr) {
    if(cr < P || P < cl) return 0;
    if(cl == cr) {
      val = GreaterFinder(x);
      return 0;
    } 
    return 1;
  });
  
  a[P] = x;
  
  sum.walk(1, 1, [&](Sum& val, int cl, int cr) {
    if(cr < P || P < cl) return 0;
    if(cl == cr) {
      val = Sum(x);
      return 0;
    } 
    return 1;
  });
  
  V = getIntervs(P);
  if(P > 1) T = getIntervs(P - 1), copy(all(T), back_inserter(V));
  if(P < n) T = getIntervs(P + 1), copy(all(T), back_inserter(V));
 
  for(auto [l, r] : V)
    Segments::insert(l, r);
    
  return;
}
 
int query(int l, int r) {
  int answer = l, ptr = l;
  while(ptr <= r) {
    ptr = Finders::nextBreaker(l, ptr);
    if(ptr <= r) answer = ptr;
  }
  
  l = answer;
  
  answer = ptr = r;
  while(ptr >= l) {
    ptr = Finders::prevBreaker(r, ptr);
    if(ptr >= l) answer = ptr;
  }
  
  r = answer;
  
  MinCounter cnt(1e9 + 5, -1, 0), cnt2;
  
  mncnt.walk(0, 1, [&](MinCounter& val, int cl, int cr) {
    if(cr < l || r < cl) return 0;
    if(l <= cl && cr <= r) {
      cnt.pull(cnt, val);
      return 0;
    }
    return 1;
  });
  
  return cnt.cnt;
}
 
 
signed main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  
  using namespace Finders;
  
  finder.init(n);
  mncnt.init(n);
  sum.init(n);
  
  finder.walk(1, 1, [&](GreaterFinder& val, int cl, int cr) { if(cl != cr) return 1; val = GreaterFinder(a[cl]); return 0;});
  mncnt.walk(1, 1, [&](MinCounter& val, int cl, int cr) { if(cl != cr) return 1; val = MinCounter(0, 1); return 0;});
  sum.walk(1, 1, [&](Sum& val, int cl, int cr) { if(cl != cr) return 1; val = Sum(a[cl]); return 0;});
  
  vector<pii> V, T;
  for(int i = 1; i <= n; i++) {
    T = getIntervs(i);
    copy(all(T), back_inserter(V));
  }
  
  for(auto [l, r] : V) {
    Segments::insert(l, r);
  }
  
  int q;
  cin >> q;
  for(int TC = 0, t, x, y; TC < q; TC++) {
    cin >> t >> x >> y;
    if(t == 1)
      updPoz(x, y);
    else
      cout << query(x, y) << '\n';
  }
}
 
/**
      Anul asta se da centroid.
-- Surse oficiale
*/

Compilation message (stderr)

fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(int, int, int) [with Node = Sum; tii = std::tuple<int, int, int>]':
fish2.cpp:41:24:   required from 'void AINT<Node>::walk(CB&&, int, int, int) [with int ismutable = 0; int toRight = 0; CB = getsum(int, int)::<lambda(Sum&, int, int)>&; Node = Sum]'
fish2.cpp:30:50:   required from 'void AINT<Node>::walk(int, int, CB&&) [with CB = getsum(int, int)::<lambda(Sum&, int, int)>; Node = Sum]'
fish2.cpp:98:141:   required from here
fish2.cpp:27:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   tii getsons(int node, int cl, int cr) { int mid = cl + cr >> 1; return tii{mid, node + 1, node + (mid - cl + 1) * 2};}
      |                                                     ~~~^~~~
fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(int, int, int) [with Node = GreaterFinder; tii = std::tuple<int, int, int>]':
fish2.cpp:41:24:   required from 'void AINT<Node>::walk(CB&&, int, int, int) [with int ismutable = 0; int toRight = 0; CB = Finders::nextGreater(int, ll)::<lambda(GreaterFinder&, int, int)>&; Node = GreaterFinder]'
fish2.cpp:30:50:   required from 'void AINT<Node>::walk(int, int, CB&&) [with CB = Finders::nextGreater(int, ll)::<lambda(GreaterFinder&, int, int)>; Node = GreaterFinder]'
fish2.cpp:113:171:   required from here
fish2.cpp:27:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(int, int, int) [with Node = MinCounter; tii = std::tuple<int, int, int>]':
fish2.cpp:41:24:   required from 'void AINT<Node>::walk(CB&&, int, int, int) [with int ismutable = 0; int toRight = 0; CB = Segments::erase(int, int)::<lambda(MinCounter&, int, int)>&; Node = MinCounter]'
fish2.cpp:30:50:   required from 'void AINT<Node>::walk(int, int, CB&&) [with CB = Segments::erase(int, int)::<lambda(MinCounter&, int, int)>; Node = MinCounter]'
fish2.cpp:205:8:   required from here
fish2.cpp:27:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17