oj.uz

Submission #746582

# Submission time Handle Problem Language Result Execution time Memory
746582 2023-05-22T21:06:21 Z arthur_nascimento Fish 2 (JOI22_fish2) C++14
31 / 100
 154 ms 24100 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];
 
			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

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 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 69 ms 14432 KB Output is correct
3 Correct 78 ms 14700 KB Output is correct
4 Correct 73 ms 14500 KB Output is correct
5 Correct 73 ms 14760 KB Output is correct
6 Correct 85 ms 16264 KB Output is correct
7 Correct 83 ms 15452 KB Output is correct
8 Correct 101 ms 16248 KB Output is correct
9 Correct 82 ms 15548 KB Output is correct
10 Correct 83 ms 15248 KB Output is correct
11 Correct 75 ms 15564 KB Output is correct
12 Correct 91 ms 15600 KB Output is correct
13 Correct 89 ms 15612 KB Output is correct
14 Correct 89 ms 15608 KB Output is correct
15 Correct 94 ms 15372 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 69 ms 14432 KB Output is correct
3 Correct 78 ms 14700 KB Output is correct
4 Correct 73 ms 14500 KB Output is correct
5 Correct 73 ms 14760 KB Output is correct
6 Correct 85 ms 16264 KB Output is correct
7 Correct 83 ms 15452 KB Output is correct
8 Correct 101 ms 16248 KB Output is correct
9 Correct 82 ms 15548 KB Output is correct
10 Correct 83 ms 15248 KB Output is correct
11 Correct 75 ms 15564 KB Output is correct
12 Correct 91 ms 15600 KB Output is correct
13 Correct 89 ms 15612 KB Output is correct
14 Correct 89 ms 15608 KB Output is correct
15 Correct 94 ms 15372 KB Output is correct
16 Correct 5 ms 9716 KB Output is correct
17 Correct 127 ms 22968 KB Output is correct
18 Correct 130 ms 22428 KB Output is correct
19 Correct 134 ms 22792 KB Output is correct
20 Correct 122 ms 22832 KB Output is correct
21 Correct 128 ms 22984 KB Output is correct
22 Correct 139 ms 22480 KB Output is correct
23 Correct 118 ms 23076 KB Output is correct
24 Correct 123 ms 22784 KB Output is correct
25 Correct 121 ms 22984 KB Output is correct
26 Correct 131 ms 22860 KB Output is correct
27 Correct 136 ms 23992 KB Output is correct
28 Correct 146 ms 23892 KB Output is correct
29 Correct 140 ms 23892 KB Output is correct
30 Correct 139 ms 22936 KB Output is correct
31 Correct 148 ms 22908 KB Output is correct
32 Correct 145 ms 23088 KB Output is correct
33 Correct 133 ms 24100 KB Output is correct
34 Correct 140 ms 23072 KB Output is correct
35 Correct 137 ms 23848 KB Output is correct
36 Correct 154 ms 23320 KB Output is correct
37 Correct 137 ms 23132 KB Output is correct
38 Correct 140 ms 23092 KB Output is correct
39 Correct 154 ms 23340 KB Output is correct
40 Correct 143 ms 22052 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 69 ms 14432 KB Output is correct
3 Correct 78 ms 14700 KB Output is correct
4 Correct 73 ms 14500 KB Output is correct
5 Correct 73 ms 14760 KB Output is correct
6 Correct 85 ms 16264 KB Output is correct
7 Correct 83 ms 15452 KB Output is correct
8 Correct 101 ms 16248 KB Output is correct
9 Correct 82 ms 15548 KB Output is correct
10 Correct 83 ms 15248 KB Output is correct
11 Correct 75 ms 15564 KB Output is correct
12 Correct 91 ms 15600 KB Output is correct
13 Correct 89 ms 15612 KB Output is correct
14 Correct 89 ms 15608 KB Output is correct
15 Correct 94 ms 15372 KB Output is correct
16 Runtime error 13 ms 19524 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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