#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)
using lll = __int128;
using ll = long long;
using ld = long double;
const int N = 1e6 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;
int n;
int a[N];
struct fenwick
{
int bit[N];
fenwick()
{
memset(bit, 0, sizeof bit);
}
void add(int x, int v)
{
for (; x < N; x += x & -x)
bit[x] += v;
}
int upto(int x)
{
int ret = 0;
for (; x; x -= x & -x)
ret += bit[x];
return ret;
}
inline int get(int l, int r) { return upto(r) - upto(l - 1); }
} sum;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
int ans = 0;
for (int i = 0; i < n;)
{
int j = i;
while (j + 1 < n && a[j + 1] >= a[j] && sum.get(a[i] + 1, a[j + 1] - 1) == 0)
{
++j;
}
ans++;
while (i <= j)
{
sum.add(a[i], 1);
++i;
}
}
cout << ans;
return 0;
}
Compilation message
money.cpp: In function 'int main()':
money.cpp:80:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
80 | freopen("in.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
