Submission #911232

#	Time	Username	Problem	Language	Result	Execution time	Memory
911232		cadmiumsky	Fish 2 (JOI22_fish2)	C++17	48 / 100	4042 ms	45640 KiB

fish2

#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, int lim) { // urmatorul de la pozitia P >= lim
    
    //for(int i = P; i <= n; i++)
      //if(a[i] >= lim) return i;
    //return n + 1;
    
    
    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, int lim) {
    
    
    //for(int i = P; i > 0; i--)
      //if(a[i] >= lim) return i;
    //return 0;
    
    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) {
      if(getsum(L, ptr) < a[ptr + 1]) {
        return ptr + 1;
      }
      ptr = nextGreater(ptr + 1, a[ptr + 1] * 2) - 1;
    }
    return n + 1;
  }
  
  int prevBreaker(int R, int start) {
    int ptr = start;
    while(ptr > 1) {
      if(getsum(ptr, R) < a[ptr - 1]) {
        return ptr - 1;
      }
      ptr = prevGreater(ptr - 1, a[ptr - 1] * 2) + 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) {
    //cerr << L << ' ' << R << '\n';
    if(direction == 1) {
      int nvR = nextBreaker(L, R) - 1;
      //cerr << nvR << '\n';
      if(nvR == R && fail) {
        elems.emplace_back(L, R);
        //cerr << L << ' ' << R << '\n';
        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;
      //cerr << nvL << '\n';
      if(nvL == L && fail) {
        //cerr << L << ' ' << R << '\n';
        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;
  }

  //cerr << "---\ncu vectorul:\n";
  //for(int i = 1; i <= n; i++) cerr << a[i] << ' '; cerr << '\n';
  //cerr << P << " apartine urmatoarelor segmente:\n";
  //for(auto [l, r] : elems)
    //cerr << l << ", " << r << '\n';
  //cerr << "----\n";
  
  //cerr << "----\n";
  
  return elems;
}


namespace Segments {
  set<pii> appearingIntervs;
  
  void erase(int l, int r) {
    if(appearingIntervs.count(pii{l, r})) {
      appearingIntervs.erase(pii{l, r});
      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(!appearingIntervs.count(pii{l, r})) {
      appearingIntervs.insert(pii{l, r});
      
      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) {
  //cerr << "=====\n";
  //cerr << "=====\n";
  //cerr << "=====\n";
  
  vector<pii> V = getIntervs(P), T;
  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(int i = 1; i <= n; i++)
    //cerr << a[i] << ' ';
  //cerr << '\n';
  //cerr << P << " --> " << x << '\n';
  
  //for(auto [l, r] : Segments::appearingIntervs) cerr << l << ", " << r << '\n';
  
  //cerr << "stergem\n";
  
  for(auto [l, r] : V)
    //cerr << l << ' ' << r << '\n',
    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(int i = 1; i <= n; i++)
    //cerr << a[i] << ' ';
  //cerr << '\n';
  //cerr << "inseram\n";
 
  for(auto [l, r] : V)
    //cerr << l << ' ' << r << '\n',
    Segments::insert(l, r);
    
  return;
}

int query(int l, int r) {
  
  //cerr << "----\n";
  
  //cerr << l << ' ' << r << '\n';
  //for(int i = l; i <= r; i++)
    //cerr << a[i] << ' ';
  //cerr << '\n';
  
  //for(auto [l, r] : Segments::appearingIntervs) cerr << l << ' ' << r << '\n';
  
  int answer = l, ptr = l;
  while(ptr <= r) {
    ptr = Finders::nextBreaker(l, ptr);
    if(ptr <= r) answer = ptr;
    //ptr = Finders::nextGreater(ptr, a[ptr] + 1);
  }
  
  l = answer;
  
  answer = ptr = r;
  while(ptr >= l) {
    //cerr << ptr << " --> ";
    ptr = Finders::prevBreaker(r, ptr);
    //cerr << ptr << '\n';
    if(ptr >= l) answer = ptr;
    //ptr = Finders::prevGreater(ptr, a[ptr] + 1);
  }
  
  r = answer;
  
  //cerr << "morph to " << l << ' ' << r << '\n';
  
  MinCounter cnt(1e9 + 5, -1, 0);
  
  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);
  
  //cerr << "initializam si noi?..";
  
  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;});
  
  //cerr << "sau hmphhphph\n";
  
  vector<pii> V, T;
  for(int i = 1; i <= n; i++) {
    T = getIntervs(i);
    copy(all(T), back_inserter(V));
  }
  
  //cerr << "Ai fi crezut ca dupa 89 ne-am fi potolit\n";
  
  for(auto [l, r] : V) {
    Segments::insert(l, r);
  }
  
  //cerr << "Mai bine de atat\n";
  
  int q;
  cin >> q;
  for(int TC = 0, t, x, y; TC < q; TC++) {
    //cerr << "o data\n";
    cin >> t >> x >> y;
    if(t == 1)
      updPoz(x, y);
    else
      cout << query(x, y) << '\n';
    //cerr << "de doua ori data\n\n";
  }
}

/**
      Anul asta se da centroid.
-- Surse oficiale
*/

Compilation message (stderr)

fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(ll, ll, ll) [with Node = Sum; tii = std::tuple<long long int, long long int, long long int>; ll = long long int]':
fish2.cpp:40:24:   required from 'void AINT<Node>::walk(CB&&, ll, ll, ll) [with long long int ismutable = 0; long long int toRight = 0; CB = getsum(ll, ll)::<lambda(Sum&, ll, ll)>&; Node = Sum; ll = long long int]'
fish2.cpp:29:50:   required from 'void AINT<Node>::walk(ll, ll, CB&&) [with CB = getsum(ll, ll)::<lambda(Sum&, ll, ll)>; Node = Sum; ll = long long int]'
fish2.cpp:97:141:   required from here
fish2.cpp:26:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   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(ll, ll, ll) [with Node = GreaterFinder; tii = std::tuple<long long int, long long int, long long int>; ll = long long int]':
fish2.cpp:40:24:   required from 'void AINT<Node>::walk(CB&&, ll, ll, ll) [with long long int ismutable = 0; long long int toRight = 0; CB = Finders::nextGreater(ll, ll)::<lambda(GreaterFinder&, ll, ll)>&; Node = GreaterFinder; ll = long long int]'
fish2.cpp:29:50:   required from 'void AINT<Node>::walk(ll, ll, CB&&) [with CB = Finders::nextGreater(ll, ll)::<lambda(GreaterFinder&, ll, ll)>; Node = GreaterFinder; ll = long long int]'
fish2.cpp:118:171:   required from here
fish2.cpp:26:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
fish2.cpp: In instantiation of 'tii AINT<Node>::getsons(ll, ll, ll) [with Node = MinCounter; tii = std::tuple<long long int, long long int, long long int>; ll = long long int]':
fish2.cpp:40:24:   required from 'void AINT<Node>::walk(CB&&, ll, ll, ll) [with long long int ismutable = 0; long long int toRight = 0; CB = Segments::erase(ll, ll)::<lambda(MinCounter&, ll, ll)>&; Node = MinCounter; ll = long long int]'
fish2.cpp:29:50:   required from 'void AINT<Node>::walk(ll, ll, CB&&) [with CB = Segments::erase(ll, ll)::<lambda(MinCounter&, ll, ll)>; Node = MinCounter; ll = long long int]'
fish2.cpp:225:8:   required from here
fish2.cpp:26: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: 0 / 35
• Subtask 6: 0 / 17