oj.uz

Submission #746236

# Submission time Handle Problem Language Result Execution time Memory
746236 2023-05-22T02:56:39 Z arthur_nascimento Fish 2 (JOI22_fish2) C++14
0 / 100
 74 ms 14476 KB 
#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];

			int 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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 74 ms 14476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 74 ms 14476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 74 ms 14476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -