Submission #746702

#	Time	Username	Problem	Language	Result	Execution time	Memory
746702		arthur_nascimento	Fish 2 (JOI22_fish2)	C++14	13 / 100	4054 ms	15308 KiB

fish2

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <ctime>
using namespace std;
 
#define maxn 200200
#define pb push_back
#define debug 
#define pii pair<int,int>
#define ll long long
#define mod 998244353
#define inf (1<<30)
 
int v_ord[maxn];
int v_rev[maxn];
 
struct query {
	int l, r, id;
	query(int l=0,int r=0,int id=0): l(l), r(r), id(id) {}
};
 
int ans[maxn];
 
int stck[maxn];
int ans_acc[maxn];
int sz;
 
vector<query> Q[maxn];
vector<int> event[maxn];
 
ll acc[maxn];
 
ll sum(int a,int b){
	ll r = acc[b];
	if(a) r -= acc[a-1];
	return r;
}
 
int greater_L[maxn];
int greater_R[maxn];
 
int value[maxn];
 
void erase(set<int> &S,int a){
	if(S.find(a) != S.end()) S.erase(a);
}
 
void solve(int *fish, int n, int eps , vector<query> vq){
 
	debug("hey\n");
 
	stck[0] = 0;
	ans_acc[0] = 0;
	sz = 1;
 
	for(int i=0;i<n;i++){
 
		acc[i] = fish[i];
		if(i) acc[i] += acc[i-1];
 
		Q[i].clear();
		event[i].clear();
 
		value[i] = 1;
 
	}
 
	for(auto q : vq)
		Q[q.r].pb(q);
 
	set<int> S, happy, unhappy;
	unhappy.insert(n+1);
	happy.insert(-1);
 
	for(int i=1;i<n-1;i++){
 
		while(fish[i] + eps > fish[stck[sz-1]]){
 
			int rem = stck[sz-1];
			greater_R[rem] = i;
 
			int jmp = i;
			if(fish[i] + eps > fish[stck[sz-2]])
				jmp = stck[sz-2];
 
			ll eats = sum(greater_L[rem] + 1, greater_R[rem] - 1), survives = 0;
			if(eats >= fish[jmp])
				value[jmp] += value[rem], survives = 1;
 
			erase(S, stck[sz-1]);
			erase(happy, stck[sz-1]);
			erase(unhappy, stck[sz-1]);
			debug("pop %d, eats %d, surv %d jmp %d\n",stck[sz-1],eats,survives,jmp);
			sz--;
 
		}
 
		greater_L[i] = stck[sz-1];
		ans_acc[i] = value[i] + ans_acc[stck[sz-1]];
 
		stck[sz++] = i;
 
		int lo = i, hi = n;
		while(lo < hi){
			int mid = (lo+hi)/2;
			if(sum(greater_L[i]+1,mid) >= fish[greater_L[i]])
				hi = mid;
			else
				lo = mid+1;
		}
 
		event[lo].pb(i);
		debug("i %d gr_L %d walk_R %d\n\n",i,greater_L[i],lo); 
 
		S.insert(i);
		unhappy.insert(i);
 
		for(int a : event[i]){
			if(S.find(a) != S.end()){
				unhappy.erase(a);
				happy.insert(a);
			}
		}
 
		for(auto q : Q[i]){
			int L = q.l;
			int top = 0;
			while(stck[top] < L) top++;
			int last_good = top;
			while(last_good+1 < sz){
				int cur = stck[last_good+1];
				if(sum(greater_L[cur]+1, i) >= fish[greater_L[cur]]) last_good++;
				else break;
			}	
			
			ans[q.id] += ans_acc[stck[last_good]] - ans_acc[stck[top]];
		}
	
	}
 
}
 
int 
main(){
 
	int n,q;
	scanf("%d",&n);
 
	for(int i=1;i<=n;i++){
		scanf("%d",v_ord+i);
		v_rev[n-i+1] = v_ord[i];
	}
 
	v_ord[0] = v_ord[n+1] = v_rev[0] = v_rev[n+1] = inf;
 
	scanf("%d",&q);
 
	vector<query> vq;
 
	for(int i=0;i<q;i++){
 
		int l,r;
        int ty;
		scanf("%d%d%d",&ty,&l,&r);
 
        if(ty == 1){
            v_ord[l] = r;
            v_rev[n-l+1] = r;
        }
        else {
            vq.clear();
            ans[0] = 0;
            vq.pb(query(l,r,0));
            solve(v_ord, n+2, 0, vq);
 
            for(auto &e : vq){
                e.l = n - e.l + 1;
                e.r = n - e.r + 1;
                swap(e.l,e.r);
            }
        
            solve(v_rev, n+2, 1, vq);
        
            printf("%d\n",1+ans[0]);
 
        }
		//vq.pb(query(l,r,i));
 
	}
 
}

Compilation message (stderr)

fish2.cpp: In function 'void solve(int*, int, int, std::vector<query>)':
fish2.cpp:54:8: warning: statement has no effect [-Wunused-value]
   54 |  debug("hey\n");
      |       ~^~~~~~~~
fish2.cpp:97:10: warning: left operand of comma operator has no effect [-Wunused-value]
   97 |    debug("pop %d, eats %d, surv %d jmp %d\n",stck[sz-1],eats,survives,jmp);
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish2.cpp:97:55: warning: right operand of comma operator has no effect [-Wunused-value]
   97 |    debug("pop %d, eats %d, surv %d jmp %d\n",stck[sz-1],eats,survives,jmp);
      |                                              ~~~~~~~~~^
fish2.cpp:97:62: warning: right operand of comma operator has no effect [-Wunused-value]
   97 |    debug("pop %d, eats %d, surv %d jmp %d\n",stck[sz-1],eats,survives,jmp);
      |                                                              ^~~~~~~~
fish2.cpp:97:71: warning: right operand of comma operator has no effect [-Wunused-value]
   97 |    debug("pop %d, eats %d, surv %d jmp %d\n",stck[sz-1],eats,survives,jmp);
      |                                                                       ^~~
fish2.cpp:117:9: warning: left operand of comma operator has no effect [-Wunused-value]
  117 |   debug("i %d gr_L %d walk_R %d\n\n",i,greater_L[i],lo);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish2.cpp:117:51: warning: right operand of comma operator has no effect [-Wunused-value]
  117 |   debug("i %d gr_L %d walk_R %d\n\n",i,greater_L[i],lo);
      |                                                   ^
fish2.cpp:117:51: warning: right operand of comma operator has no effect [-Wunused-value]
  117 |   debug("i %d gr_L %d walk_R %d\n\n",i,greater_L[i],lo);
      |                                        ~~~~~~~~~~~^
fish2.cpp: In function 'int main()':
fish2.cpp:151:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fish2.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |   scanf("%d",v_ord+i);
      |   ~~~~~^~~~~~~~~~~~~~
fish2.cpp:160:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
fish2.cpp:168:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |   scanf("%d%d%d",&ty,&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

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