oj.uz

Submission #691781

# Submission time Handle Problem Language Result Execution time Memory
691781 2023-01-31T14:23:30 Z tolbi Money (IZhO17_money) C++17
100 / 100
 1439 ms 61888 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
#ifdef LOCAL
	#include "23.h"
#endif
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
using namespace std;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct BIT{
	vector<int> fenwik;
	BIT(int n){
		fenwik.resize(2*n);
	}
	void update(int node){
		for (; node<fenwik.size(); node=node|(node+1)) fenwik[node]++;
	}
	int get(int node){
		int rval = 0;
		for (; node>=0; node=(node&(node+1))-1) rval+=fenwik[node];
		return rval;
	}
	int query(int l, int r){
		int hh = 0;
		if (l) hh = get(l-1);
		if (l>r) return 0ll;
		return get(r)-hh;
	}
};
void compress(vector<int> &arr){
	vector<int> barr = arr;
	map<int,int> mp;
	sortarr(barr);
	int ind = 1;
	for (int i = 0; i < arr.size(); i++){
		if (mp[barr[i]]) continue;
		mp[barr[i]]=ind++;
	}
	for (int i = 0; i < arr.size(); ++i)
	{
		arr[i]=mp[arr[i]];
	}
}
int32_t main(){
	ios;
	int t=1;
	int tno = 0;
	if (!t) cin>>t;
	while (t-(tno++)){
		deci(n);
		vint(arr(n));
		cinarr(arr);
		compress(arr);
		BIT fenwik(n);
		int ans = n;
		fenwik.update(arr[0]);
		vector<int> barr=arr;
		int ind = 1;
		for (int i = 1; i < n; i++){
			if (arr[i]>=barr[i-1]){
				if (fenwik.query(arr[i-1]+1,arr[i]-1)==0){
					ans--;
					arr[i]=arr[i-1];
				}
				else {
					while (ind<=i){
						fenwik.update(barr[ind++]);
					}
				}
			}
			else {
				while (ind<=i){
					fenwik.update(barr[ind++]);
				}
			}
		}
		cout<<ans<<endl;
	}
}

Compilation message

money.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
money.cpp: In member function 'void BIT::update(int)':
money.cpp:38:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (; node<fenwik.size(); node=node|(node+1)) fenwik[node]++;
      |          ~~~~^~~~~~~~~~~~~~
money.cpp: In function 'void compress(std::vector<int>&)':
money.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < arr.size(); i++){
      |                  ~~^~~~~~~~~~~~
money.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < arr.size(); ++i)
      |                  ~~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 1 ms 324 KB Output is correct
22 Correct 1 ms 320 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 320 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 324 KB Output is correct
35 Correct 0 ms 324 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 1 ms 324 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 83 ms 8520 KB Output is correct
40 Correct 150 ms 13388 KB Output is correct
41 Correct 66 ms 7088 KB Output is correct
42 Correct 60 ms 6476 KB Output is correct
43 Correct 40 ms 4820 KB Output is correct
44 Correct 211 ms 16748 KB Output is correct
45 Correct 185 ms 16732 KB Output is correct
46 Correct 190 ms 16656 KB Output is correct
47 Correct 169 ms 16720 KB Output is correct
48 Correct 178 ms 16752 KB Output is correct
49 Correct 659 ms 27468 KB Output is correct
50 Correct 661 ms 27468 KB Output is correct
51 Correct 683 ms 27604 KB Output is correct
52 Correct 691 ms 27404 KB Output is correct
53 Correct 685 ms 27400 KB Output is correct
54 Correct 670 ms 27436 KB Output is correct
55 Correct 1439 ms 55936 KB Output is correct
56 Correct 1432 ms 61880 KB Output is correct
57 Correct 1417 ms 61864 KB Output is correct
58 Correct 1417 ms 61860 KB Output is correct
59 Correct 1412 ms 61856 KB Output is correct
60 Correct 1418 ms 61888 KB Output is correct
61 Correct 1392 ms 61856 KB Output is correct
62 Correct 1426 ms 61872 KB Output is correct