Submission #1187313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187313		epicci23	Fish 2 (JOI22_fish2)	C++20	100 / 100	1874 ms	115372 KiB

fish2

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int) a.size()
using namespace std;

// base impl ile baslayalim sonra gelistiririz adim adim

const int N = 100005;
int n, q, ar[N];

struct Info{
  int sum, l, r;
  vector<int> il, ir, sl, sr, vl, vr;
  void init(int ind, int val){
    sum = val;
    l = r = ind;
    il.clear(),ir.clear(),sl.clear(),sr.clear(),vl.clear(),vr.clear();
    il.push_back(ind), ir.push_back(ind);
    sl.push_back(val), sr.push_back(val);
    vl.push_back(1), vr.push_back(1);
  }
};

Info T[4 * N], BOS;

Info merge(Info lf, Info rg){ // try ampersand??
 if(lf.l == -1) return rg;
 if(rg.r == -1) return lf;
 Info res;
 res.sum = lf.sum + rg.sum;
 res.l = lf.l, res.r = rg.r;
  
 for(int i = 0; i < sz(lf.il); i++){
  res.il.push_back(lf.il[i]);
  res.sl.push_back(lf.sl[i]);
  res.vl.push_back(0);
 }

 for(int i = 0; i < sz(rg.ir); i++){
  res.ir.push_back(rg.ir[i]);
  res.sr.push_back(rg.sr[i]);
  res.vr.push_back(0);
 }

 int cur = lf.sum, p = 0;
 
 while(p < sz(rg.sl)){
   if(cur < ar[rg.il[p]]){
    res.il.push_back(rg.il[p]);
    res.sl.push_back(rg.sl[p]); 
    res.vl.push_back(0);
   }
   else res.sl[sz(res.sl) - 1] += rg.sl[p];
   cur += rg.sl[p++];
 }

 cur = rg.sum, p = 0;

 while(p < sz(lf.sr)){
   if(cur < ar[lf.ir[p]]){
    res.ir.push_back(lf.ir[p]);
    res.sr.push_back(lf.sr[p]);
    res.vr.push_back(0); 
   }
   else res.sr[sz(res.sr) - 1] += lf.sr[p];
   cur += lf.sr[p++];
 }
 
 int j = 0, pl = 0, pr = 0, sm = 0;
 for(int i = 0; i < sz(rg.il); i++){ // OPTIMIZE THIS!!!!
   if(i + 1 > pr) sm += rg.sl[pr++];
   
   while(pl < sz(lf.ir) || pr < sz(rg.il)){
    if(pl < sz(lf.ir) && sm >= ar[lf.ir[pl]]) sm += lf.sr[pl++];
    else if(pr < sz(rg.il) && sm >= ar[rg.il[pr]]) sm += rg.sl[pr++];
    else break;
   }

   if(pl < sz(lf.ir)) continue;
   
   for(;j < sz(res.il);){
     if(j == sz(res.il) - 1 || sm < ar[res.il[j+1]]){
       res.vl[j] += rg.vl[i];
       break;
     }
     else j++;
   }
 }

 j = 0, pl = 0, pr = 0, sm = 0;
 for(int i = 0; i < sz(lf.ir); i++){ // OPTIMIZE THIS!!!!
   if(i + 1 > pl) sm += lf.sr[pl++];

   while(pl < sz(lf.ir) || pr < sz(rg.il)){
    if(pl < sz(lf.ir) && sm >= ar[lf.ir[pl]]) sm += lf.sr[pl++];
    else if(pr < sz(rg.il) && sm >= ar[rg.il[pr]]) sm += rg.sl[pr++];
    else break;
   }

   if(pl < sz(lf.ir)) continue;
   
   for(;j < sz(res.il);){
     if(j == sz(res.il) - 1 || sm < ar[res.il[j+1]]){
       res.vl[j] += lf.vr[i];
       break;
     }
     else j++;
   }
 }

 j = 0, pl = 0, pr = 0, sm = 0;
 for(int i = 0; i < sz(lf.ir); i++){ // OPTIMIZE THIS!!!!
   if(i + 1 > pl) sm += lf.sr[pl++];

   while(pl < sz(lf.ir) || pr < sz(rg.il)){
    if(pl < sz(lf.ir) && sm >= ar[lf.ir[pl]]) sm += lf.sr[pl++];
    else if(pr < sz(rg.il) && sm >= ar[rg.il[pr]]) sm += rg.sl[pr++];
    else break;
   }

   if(pr < sz(rg.il)) continue;
   
   for(;j < sz(res.ir);){
     if(j == sz(res.ir) - 1 || sm < ar[res.ir[j+1]]){
       res.vr[j] += lf.vr[i];
       break;
     }
     else j++;
   }
 }

 j = 0, pl = 0, pr = 0, sm = 0;
 for(int i = 0; i < sz(rg.il); i++){ // OPTIMIZE THIS!!!!
   if(i + 1 > pr) sm += rg.sl[pr++];

   while(pl < sz(lf.ir) || pr < sz(rg.il)){
    if(pl < sz(lf.ir) && sm >= ar[lf.ir[pl]]) sm += lf.sr[pl++];
    else if(pr < sz(rg.il) && sm >= ar[rg.il[pr]]) sm += rg.sl[pr++];
    else break;
   }

   if(pr < sz(rg.il)) continue;
   
   for(;j < sz(res.ir);){
     if(j == sz(res.ir) - 1 || sm < ar[res.ir[j+1]]){
       res.vr[j] += rg.vl[i];
       break;
     }
     else j++;
   }
 }
  
 for(int i = 0; i + 1 < sz(lf.il); i++) res.vl[i] += lf.vl[i];
 for(int i = 0; i + 1 < sz(rg.ir); i++) res.vr[i] += rg.vr[i];
 
 return res;
}

void build(int rt, int l, int r){
  if(l == r){
   T[rt].init(l, ar[l]);
   return;
  }
  int mid = (l + r) / 2;
  build(rt * 2, l, mid), build(rt * 2 + 1, mid + 1, r);

  T[rt] = merge(T[rt * 2], T[rt * 2 + 1]);

  /*cout << "bura nasil : " << l << ' ' << r <<  '\n';

  cout << "pree\n";

  for(int i = 0; i < sz(T[rt].vl); i++){
   cout << "bakalimm : " << i << '\n';
   cout << T[rt].il[i] << ' ' << T[rt].sl[i] << ' ' << T[rt].vl[i] << '\n';
  }

  cout << "suff\n";
 
  for(int i = 0; i < sz(T[rt].vr); i++){
   cout << "bakalimm : " << i << '\n';
   cout << T[rt].ir[i] << ' ' << T[rt].sr[i] << ' ' << T[rt].vr[i] << '\n';
  }*/
}

void upd(int rt,int l,int r,int ind){
  if(r < ind || l > ind) return;
  if(l == r){
   T[rt].init(l, ar[l]);
   return;
  }

  int mid = (l + r) / 2;
  upd(rt * 2, l, mid, ind), upd(rt * 2 + 1, mid + 1, r, ind);
  T[rt] = merge(T[rt * 2], T[rt * 2 + 1]);
}

Info Query(int rt, int l, int r, int gl, int gr){
  //cout << "neredeyim : " << l << ' ' << r << '\n';
  if(r < gl || l > gr) return BOS;
  if(l >= gl && r <= gr) return T[rt];
  
  int mid = (l + r) / 2;
  
  Info CUR = merge(Query(rt * 2, l, mid, gl, gr), Query(rt * 2 + 1, mid + 1, r, gl, gr));

  /*cout << "gel gel : " << l << ' ' << r << '\n';

  cout << "ranges : " << CUR.l << ' ' << CUR.r << '\n';
  cout << "tot : " << CUR.sum << '\n';

  cout << "pree\n";

  for(int i = 0; i < sz(CUR.vl); i++){
   cout << "bakalimm : " << i << '\n';
   cout << CUR.il[i] << ' ' << CUR.sl[i] << ' ' << CUR.vl[i] << '\n';
  }

  cout << "suff\n";
 
  for(int i = 0; i < sz(CUR.vr); i++){
   cout << "bakalimm : " << i << '\n';
   cout << CUR.ir[i] << ' ' << CUR.sr[i] << ' ' << CUR.vr[i] << '\n';
  }*/


  return CUR;
}

void _(){
  cin >> n;
  for(int i=1;i<=n;i++) cin >> ar[i];

  build(1,1,n);

  BOS.init(-1, -1);
  cin >> q;

  while(q--){
  	int op;
  	cin >> op;
  	if(op == 1){
      int ind, val;
      cin >> ind >> val;
      ar[ind] = val;
      upd(1,1,n,ind);
  	}
  	else{
      int l, r;
      cin >> l >> r;
      
      Info X = Query(1,1,n,l,r);
      cout << X.vl.back() << '\n';
  	}
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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