답안 #439801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
439801 2021-06-30T19:40:12 Z LastRonin Money (IZhO17_money) C++14
100 / 100
748 ms 31424 KB
#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;
      |     ^~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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