Submission #888123

#	Time	Username	Problem	Language	Result	Execution time	Memory
888123		sleepntsheep	Financial Report (JOI21_financial)	C++17	5 / 100	173 ms	59100 KiB

Main

#include <iostream>
#include <stack>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
using pt = complex<f80>;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

struct segment_tree
{
    vector<int> t;
    int n;
    segment_tree(int n0) : n(n0), t(n0<<1) {}
    stack<pair<int, int>> save;
    stack<unsigned> savepoint;

    void __set(int p, int k)
    {
        save.emplace(p, t[p]);
        t[p] = k;
    }

    void chmax(int p, int k)
    {
        savepoint.push(save.size());
        for (p += n, __set(p, max(t[p], k)); p >>= 1;) __set(p, max(t[p<<1], t[p<<1|1]));
    }

    int query(int l, int r)
    {
        int z{0};
        for (l += n, r += n; l < r; l >>= 1, r >>= 1)
        {
            if (l&1) z = max(z, t[l++]);
            if (r&1) z = max(t[--r], z);
        }
        return z;
    }

    void rollback()
    {
        while (save.size() > savepoint.top())
        {
            auto [p, tp] = save.top();
            t[p] = tp;
            save.pop();
        }
        savepoint.pop();
    }
};

class queue_segment_tree
{
    public:
    segment_tree t;

    struct update
    {
        char type;
        int p, k;
    };

    unsigned bottom = 0;
    vector<update> S;

    queue_segment_tree(int n) : t(n) {}

    void chmax(int p, int k) { S.emplace_back(update{'B', p, k}); t.chmax(p, k); }

    int query(int l, int r) { return t.query(l, r); }

    void pop()
    {
        bottomify();
        if (bottom == S.size()) new_phase();
        fix();
        t.rollback();
        S.pop_back();
    }

    private:
    void bottomify()
    {
        while (bottom < S.size() && S[bottom].type == 'B') ++bottom;
    }

    void fix()
    {
        if (S.back().type == 'A') return;
        bottomify();
        vector<update> s[2];
        while (S.size() > bottom && (s[0].empty() || s[0].size() != s[1].size()))
        {
            s[S.back().type == 'B'].emplace_back(S.back());
            t.rollback(); S.pop_back();
        }
        for (auto j : {1, 0}) for (auto it = rbegin(s[j]); it != rend(s[j]); ++it) S.push_back(*it), t.chmax(it->p, it->k);
        bottomify();
    }

    void new_phase()
    {
        for (auto &_ : S) t.rollback();
        reverse(ALL(S));
        for (auto &x : S) t.chmax(x.p, x.k), x.type = 'A';
        bottom = 0;
    }
};

int main()
{
    ShinLena;
    int n, d;
    cin >> n >> d;
    vector<int> a(n), c;
    for (auto &x : a) cin >> x;
    c = a;
    sort(ALL(c));
    for (auto &x : a) x = lower_bound(ALL(c), x) - c.begin();

    queue_segment_tree t(c.size());
    int l = 0, z = 0;
    for (int i = 0; i < n; ++i)
    {
        if (i > d) t.pop();
        int r = t.query(0, a[i]);
        r = max(r + 1, t.query(0, a[i]+1));
        z = max(z, r);
        if (i == n - 1) return cout << z , 0;
        t.chmax(a[i], r);
    }


    return 0;
}

Compilation message (stderr)

Main.cpp: In constructor 'segment_tree::segment_tree(int)':
Main.cpp:30:9: warning: 'segment_tree::n' will be initialized after [-Wreorder]
   30 |     int n;
      |         ^
Main.cpp:29:17: warning:   'std::vector<int> segment_tree::t' [-Wreorder]
   29 |     vector<int> t;
      |                 ^
Main.cpp:31:5: warning:   when initialized here [-Wreorder]
   31 |     segment_tree(int n0) : n(n0), t(n0<<1) {}
      |     ^~~~~~~~~~~~
Main.cpp: In member function 'void queue_segment_tree::new_phase()':
Main.cpp:121:20: warning: unused variable '_' [-Wunused-variable]
  121 |         for (auto &_ : S) t.rollback();
      |                    ^
Main.cpp: In function 'int main()':
Main.cpp:140:9: warning: unused variable 'l' [-Wunused-variable]
  140 |     int l = 0, z = 0;
      |         ^

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35