Submission #746582

#	Time	Username	Problem	Language	Result	Execution time	Memory
746582		arthur_nascimento	Fish 2 (JOI22_fish2)	C++14	31 / 100	154 ms	24100 KiB

fish2

#include <bits/stdc++.h>
 
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 = *S.lower_bound(L);
			int first_bad = *unhappy.upper_bound(top);
			int last_good = *--happy.lower_bound(first_bad);
			debug("query %d: top %d, bad = %d, good = %d\n",q.id,top,first_bad,last_good);
			if(last_good > top)
				ans[q.id] += ans_acc[last_good] - ans_acc[top];
		}
	
	}
 
}
 
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;
		scanf("%*d%d%d",&l,&r);
 
		vq.pb(query(l,r,i));
 
	}
 
	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);
 
	for(int i=0;i<q;i++)
		printf("%d\n",ans[i]+1);
 
}

Compilation message (stderr)

fish2.cpp: In function 'void solve(int*, int, int, std::vector<query>)':
fish2.cpp:57:8: warning: statement has no effect [-Wunused-value]
   57 |  debug("hey\n");
      |       ~^~~~~~~~
fish2.cpp:100:10: warning: left operand of comma operator has no effect [-Wunused-value]
  100 |    debug("pop %d, eats %d, surv %d jmp %d\n",stck[sz-1],eats,survives,jmp);
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish2.cpp:100:55: warning: right operand of comma operator has no effect [-Wunused-value]
  100 |    debug("pop %d, eats %d, surv %d jmp %d\n",stck[sz-1],eats,survives,jmp);
      |                                              ~~~~~~~~~^
fish2.cpp:100:62: warning: right operand of comma operator has no effect [-Wunused-value]
  100 |    debug("pop %d, eats %d, surv %d jmp %d\n",stck[sz-1],eats,survives,jmp);
      |                                                              ^~~~~~~~
fish2.cpp:100:71: warning: right operand of comma operator has no effect [-Wunused-value]
  100 |    debug("pop %d, eats %d, surv %d jmp %d\n",stck[sz-1],eats,survives,jmp);
      |                                                                       ^~~
fish2.cpp:120:9: warning: left operand of comma operator has no effect [-Wunused-value]
  120 |   debug("i %d gr_L %d walk_R %d\n\n",i,greater_L[i],lo);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish2.cpp:120:51: warning: right operand of comma operator has no effect [-Wunused-value]
  120 |   debug("i %d gr_L %d walk_R %d\n\n",i,greater_L[i],lo);
      |                                                   ^
fish2.cpp:120:51: warning: right operand of comma operator has no effect [-Wunused-value]
  120 |   debug("i %d gr_L %d walk_R %d\n\n",i,greater_L[i],lo);
      |                                        ~~~~~~~~~~~^
fish2.cpp:137:10: warning: left operand of comma operator has no effect [-Wunused-value]
  137 |    debug("query %d: top %d, bad = %d, good = %d\n",q.id,top,first_bad,last_good);
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish2.cpp:137:54: warning: right operand of comma operator has no effect [-Wunused-value]
  137 |    debug("query %d: top %d, bad = %d, good = %d\n",q.id,top,first_bad,last_good);
      |                                                    ~~^~
fish2.cpp:137:61: warning: right operand of comma operator has no effect [-Wunused-value]
  137 |    debug("query %d: top %d, bad = %d, good = %d\n",q.id,top,first_bad,last_good);
      |                                                             ^~~~~~~~~
fish2.cpp:137:71: warning: right operand of comma operator has no effect [-Wunused-value]
  137 |    debug("query %d: top %d, bad = %d, good = %d\n",q.id,top,first_bad,last_good);
      |                                                                       ^~~~~~~~~
fish2.cpp: At global scope:
fish2.cpp:146:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  146 | main(){
      | ^~~~
fish2.cpp: In function 'int main()':
fish2.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fish2.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d",v_ord+i);
      |   ~~~~~^~~~~~~~~~~~~~
fish2.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
fish2.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   scanf("%*d%d%d",&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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