Submission #439801

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
439801	2021-06-30T19:40:12 Z	LastRonin	Money (IZhO17_money)	C++14	100 / 100	748 ms	31424 KB

money

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define si short int
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pill pair<ll,ll>
#define f first
#define s second
#define pilc pair<ll,char>
#define all(a) (a).begin(),(a).end()
#define rep(s,e,step) for(int i = (s); i < (e) ; i += step)
#define vrep(s,e,step) for(int j = (s); j < (e) ; j += step)
#define ex exit(0) 
#define sz(a) (a).size()
#define triple pair<pill, ll>
#define pinode pair<node*, node*>
#define quadra pair<pill, pill>
#define ld long double
using namespace std;
 
const ll N = 1e6 + 10;
const ll M = 1e4 + 10;
const ll big = 1e17;
const ll hsh2 = 1964325029;
const long long mod = 1e9 + 7;
const long double EPS = 1e-10;
const ll block = 1e7;
const ll shift = 2e3;
const ld pi = acos(-1.0);
 
ll n, m;
 
ll a[N], was[N];
 
ll t[4 * N];
 
void upd(ll p, ll v = 1, ll tl = 1, ll tr = 1e6) {	
	if(tl == tr)
		return (void)(t[v]++);
	ll m = (tl + tr) >> 1ll;
	if(p <= m)
		upd(p, v * 2, tl, m);
	else
		upd(p, v * 2 + 1, m + 1, tr);
	t[v] = t[v * 2] + t[v * 2 + 1];
}
ll get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = 1e6) {
	if(l > tr || tl > r)
		return 0;
	if(l <= tl && tr <= r)
		return t[v];
	ll m = (tl + tr) >> 1ll;
	return get(l, r, v * 2, tl, m) + get(l, r, v * 2 + 1, m + 1, tr);	
}
 
int main() {
	speed;
	cin >> n;
	ll ans = 1;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	ll str = -1;
	for(int i = 1; i < n; i++) {
		if(str == -1)
			str = i;
		if(a[i] > a[i + 1]) {
		    for(int j = str; j <= i; j++)
		    	upd(a[j], 1);
			ans++,str = -1;
		}
		else {
			ll can = get(a[str] + 1, a[i + 1] - 1);
			if(can) {
			    for(int j = str; j <= i; j++)
		    		upd(a[j], 1);
				str = -1;
				ans++;
			}			
		}
	}
	cout << ans << '\n';
}
/*
*/

Compilation message

money.cpp: In function 'int main()':
money.cpp:70:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |       for(int j = str; j <= i; j++)
      |       ^~~
money.cpp:72:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   72 |    ans++,str = -1;
      |    ^~~
money.cpp:77:8: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   77 |        for(int j = str; j <= i; j++)
      |        ^~~
money.cpp:79:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   79 |     str = -1;
      |     ^~~

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	460 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	1 ms	460 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	460 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	1 ms	460 KB	Output is correct
17	Correct	1 ms	460 KB	Output is correct
18	Correct	1 ms	460 KB	Output is correct
19	Correct	1 ms	460 KB	Output is correct
20	Correct	1 ms	460 KB	Output is correct
21	Correct	1 ms	460 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	460 KB	Output is correct
24	Correct	1 ms	460 KB	Output is correct
25	Correct	1 ms	716 KB	Output is correct
26	Correct	1 ms	716 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	460 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	1 ms	460 KB	Output is correct
17	Correct	1 ms	460 KB	Output is correct
18	Correct	1 ms	460 KB	Output is correct
19	Correct	1 ms	460 KB	Output is correct
20	Correct	1 ms	460 KB	Output is correct
21	Correct	1 ms	460 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	460 KB	Output is correct
24	Correct	1 ms	460 KB	Output is correct
25	Correct	1 ms	716 KB	Output is correct
26	Correct	1 ms	716 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	460 KB	Output is correct
33	Correct	1 ms	460 KB	Output is correct
34	Correct	1 ms	588 KB	Output is correct
35	Correct	1 ms	332 KB	Output is correct
36	Correct	1 ms	460 KB	Output is correct
37	Correct	3 ms	3276 KB	Output is correct
38	Correct	2 ms	3276 KB	Output is correct

Subtask #4
55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	460 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	1 ms	460 KB	Output is correct
17	Correct	1 ms	460 KB	Output is correct
18	Correct	1 ms	460 KB	Output is correct
19	Correct	1 ms	460 KB	Output is correct
20	Correct	1 ms	460 KB	Output is correct
21	Correct	1 ms	460 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	460 KB	Output is correct
24	Correct	1 ms	460 KB	Output is correct
25	Correct	1 ms	716 KB	Output is correct
26	Correct	1 ms	716 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	460 KB	Output is correct
33	Correct	1 ms	460 KB	Output is correct
34	Correct	1 ms	588 KB	Output is correct
35	Correct	1 ms	332 KB	Output is correct
36	Correct	1 ms	460 KB	Output is correct
37	Correct	3 ms	3276 KB	Output is correct
38	Correct	2 ms	3276 KB	Output is correct
39	Correct	173 ms	4348 KB	Output is correct
40	Correct	314 ms	12216 KB	Output is correct
41	Correct	139 ms	6084 KB	Output is correct
42	Correct	137 ms	5816 KB	Output is correct
43	Correct	99 ms	4388 KB	Output is correct
44	Correct	387 ms	15316 KB	Output is correct
45	Correct	378 ms	15068 KB	Output is correct
46	Correct	367 ms	15312 KB	Output is correct
47	Correct	377 ms	15148 KB	Output is correct
48	Correct	355 ms	15028 KB	Output is correct
49	Correct	578 ms	31380 KB	Output is correct
50	Correct	540 ms	31348 KB	Output is correct
51	Correct	545 ms	31280 KB	Output is correct
52	Correct	528 ms	31336 KB	Output is correct
53	Correct	563 ms	31424 KB	Output is correct
54	Correct	570 ms	31240 KB	Output is correct
55	Correct	724 ms	31300 KB	Output is correct
56	Correct	707 ms	31288 KB	Output is correct
57	Correct	748 ms	31332 KB	Output is correct
58	Correct	730 ms	31292 KB	Output is correct
59	Correct	673 ms	31300 KB	Output is correct
60	Correct	723 ms	31220 KB	Output is correct
61	Correct	696 ms	31288 KB	Output is correct
62	Correct	712 ms	31316 KB	Output is correct

Submission #439801

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 20.0 / 20.0

Subtask #4 55.0 / 55.0

Subtask #1
9.0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
20.0 / 20.0

Subtask #4
55.0 / 55.0