Submission #546367

#	Time	Username	Problem	Language	Result	Execution time	Memory
546367		ivan_tudor	Fish 2 (JOI22_fish2)	C++14	100 / 100	1366 ms	74296 KiB

fish2

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct stuck{
  int i;
  long long a;
  long long sum;
  int candi;
};
struct aint_node{
  vector<stuck> pref;
  vector<stuck> suf;
  long long sum;
  int answer;
};
const long long INF = LLONG_MAX;
aint_node join(aint_node l, aint_node r, int litv, int ritv){
  aint_node root;
  root.sum = l.sum + r.sum;
 /// folosim l.suf, r.pref
  int isuf = 0, jpref = 0;
  int candidates = 0;
  long long csum = 0;
  vector<int> newlscand(l.suf.size());
  vector<int> newrpcand(r.pref.size());
  stuck left = l.suf[0], right = r.pref[0];
  while(true ){
    if(isuf + 1 >= l.suf.size() && jpref + 1 >= r.pref.size())
			break;
		if(isuf + 1 < l.suf.size() && jpref + 1 < r.pref.size()){
			if(l.suf[isuf].a <= r.pref[jpref].a){
				isuf++;
				left = l.suf[isuf];
				candidates += left.candi;
			}
			else{
				jpref++;
				right = r.pref[jpref];
				candidates += right.candi;
			}
    }
    else{
			if(isuf + 1 < l.suf.size()){
				isuf++;
				left = l.suf[isuf];
				candidates += left.candi;
			}
			else if(jpref + 1 < r.pref.size()){
				jpref++;
				right = r.pref[jpref];
				candidates += right.candi;
			}
    }
    csum = left.sum + right.sum; /// pana aici am ajuns
    if(left.i == litv - 1){
			newrpcand[jpref] = candidates;
    }
    if(right.i == ritv + 1){
			newlscand[isuf] = candidates;
    }
    if(csum < min(left.a, right.a) && min(left.a, right.a) < INF)
      candidates = 0;
  }
  root.answer = candidates;
  ///todothis
  root.pref = l.pref;
  root.pref.pop_back();
  for(int i = 0; i < r.pref.size(); i++){
    stuck x = r.pref[i];
    if(x.a > x.sum + l.sum){
      root.pref.push_back({x.i, x.a, x.sum + l.sum, newrpcand[i] });
    }
  }
	//root.pref.push_back({ritv + 1, INF, root.sum, root.answer});
  root.suf = r.suf;
  root.suf.pop_back(); /// cel de la margine
  for(int i = 0; i < l.suf.size(); i++){
		stuck x = l.suf[i];
		if(x.a > x.sum + r.sum){
			root.suf.push_back({x.i, x.a, x.sum + r.sum, newlscand[i]});
		}
  }
  return root;
}
aint_node build(int poz, int val){
	aint_node rsp;
	rsp.sum = val;
	rsp.answer = 1;
	rsp.pref.push_back({poz, val, 0, 0});
	rsp.pref.push_back({poz + 1, INF, val, 1});
	rsp.suf.push_back({poz, val, 0, 0});
	rsp.suf.push_back({poz - 1, INF, val, 1});
	return rsp;
}
const int N = 100005;
aint_node aint[4*N];
int v[N];
void build_aint(int nod, int l, int r){
	if(l == r){
		aint[nod] = build(l, v[l]);
		return;
	}
	int mid = (l + r)/2;
	build_aint(2*nod, l, mid);
	build_aint(2*nod + 1, mid + 1, r);
	aint[nod] = join(aint[2*nod], aint[2*nod + 1], l, r);
}
void update(int nod, int l, int r, int poz, int val){
	if(poz > r || poz < l)
		return;
	if(l == r){
		aint[nod] = build(poz, val);
		return;
	}
	int mid = (l + r)/2;
	update(2*nod, l, mid, poz, val);
	update(2*nod + 1, mid + 1, r, poz, val);
	aint[nod] = join(aint[2*nod], aint[2*nod + 1], l, r);
}
aint_node query(int nod, int l, int r, int ql, int qr){
	if(ql <= l && r <= qr)
		return aint[nod];
	int mid = (l + r)/2;
	if(qr <= mid){
		return query(2*nod, l, mid, ql, qr);
	}
	if(ql >= mid + 1){
		return query(2*nod + 1, mid + 1, r, ql, qr);
	}
	aint_node ls = query(2*nod, l, mid, ql, mid);
	aint_node rs = query(2*nod + 1, mid + 1, r, mid + 1, qr);
	return join(ls, rs, ql, qr);
}
int main()
{
	int n;
	cin>>n;
	for(int i = 1; i<=n; i++)
		cin>>v[i];
	build_aint(1, 1, n);
	int q;
	cin>>q;
	for(int i = 1; i<=q; i++){
		int t;
		cin>>t;
		if(t == 1){
			int poz, val;
			cin>>poz>>val;
			update(1, 1, n, poz, val);
		}
		else{
			int l, r;
			cin>>l>>r;
			aint_node rsp = query(1, 1, n, l, r);
			cout<<rsp.answer<<"\n";
		}
	}
	return 0;
}

Compilation message (stderr)

fish2.cpp: In function 'aint_node join(aint_node, aint_node, int, int)':
fish2.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<stuck>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if(isuf + 1 >= l.suf.size() && jpref + 1 >= r.pref.size())
      |        ~~~~~~~~~^~~~~~~~~~~~~~~
fish2.cpp:28:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<stuck>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if(isuf + 1 >= l.suf.size() && jpref + 1 >= r.pref.size())
      |                                    ~~~~~~~~~~^~~~~~~~~~~~~~~~
fish2.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<stuck>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   if(isuf + 1 < l.suf.size() && jpref + 1 < r.pref.size()){
      |      ~~~~~~~~~^~~~~~~~~~~~~~
fish2.cpp:30:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<stuck>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   if(isuf + 1 < l.suf.size() && jpref + 1 < r.pref.size()){
      |                                 ~~~~~~~~~~^~~~~~~~~~~~~~~
fish2.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<stuck>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if(isuf + 1 < l.suf.size()){
      |       ~~~~~~~~~^~~~~~~~~~~~~~
fish2.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<stuck>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    else if(jpref + 1 < r.pref.size()){
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~
fish2.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<stuck>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(int i = 0; i < r.pref.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
fish2.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<stuck>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i = 0; i < l.suf.size(); i++){
      |                  ~~^~~~~~~~~~~~~~

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