제출 #1273632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273632		bbldrizzy	Money (IZhO17_money)	C++20	100 / 100	145 ms	16096 KiB

money

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
#include <set>
#include <random>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define f first
#define s second
const int MOD = 1e9+7;
const ll inf = 4*1e18;
const int mx = 5*1e5+5;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const int N = 1e6+5;

template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;

  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}

	/** Sets the value at index ind to val. */
	void set(int ind, T val) { add(ind, val - arr[ind]); }

	/** Adds val to the element at index ind. */
	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}

	/** @return The sum of all values in [0, ind]. */
	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    BIT<ll> bit(N);
    ll ans = 0;
    ll prev = -1;
    for (int i = 0; i <= n; i++) {
        ans++;
        int j = i;
        // cout << "i, j: " << i << " " << j << "\n";
        vector<int> upd;
        int edge = 0;
        while (j < n) {
            if (j == i && prev == -1) {
                int x; cin >> x;
                upd.push_back(x);
                j++;
                prev = x;
                continue;
            } else {
                if (j == i) upd.push_back(prev);
                int x; cin >> x;
                // if (i == 5) {
                //     cout << "x, prev: " << x << " " << prev << "\n";
                // }
                if (upd.size() > 1 && bit.pref_sum(x)-bit.pref_sum(x-1) > 0) {
                    edge = 1;
                } 
                if (x < prev) {
                    prev = x;
                    break;
                } else if (x == prev) {
                    j++;
                    continue;
                } else {
                    // if (i == 5) {
                    //     cout << "sigger, x, prev: " << x << " " << prev << "\n";
                    // }
                    if (edge == 0 && bit.pref_sum(x)-bit.pref_sum(prev) == 0) {
                        prev = x;
                        j++;
                        upd.push_back(x);
                        continue;
                    } else if (bit.pref_sum(x-1)-bit.pref_sum(prev) == 0 && edge == 0) {
                        edge = 1;
                        prev = x;
                        j++;
                        upd.push_back(x);
                        continue;
                    } else {
                        prev = x;
                        break;
                    }
                }
            }
        }
        // cout << "i2, j2: " << i << " " << j << "\n";
        i = j;
        for (auto x: upd) {
            bit.add(x, 1);
        }
        upd.clear();
    }
    cout << ans << "\n";
}

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