Submission #365153

#	Time	Username	Problem	Language	Result	Execution time	Memory
365153		mohamedsobhi777	Money (IZhO17_money)	C++14	100 / 100	222 ms	8684 KiB

money

#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)
       {
              if (l > r)
                     return 0;
              return upto(r) - upto(l - 1);
       }
} sum;

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#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;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55