oj.uz

답안 #888123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888123 2023-12-16T04:38:16 Z sleepntsheep Financial Report (JOI21_financial) C++17
5 / 100
 173 ms 59100 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 4944 KB Output is correct
2 Incorrect 151 ms 5136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 56828 KB Output is correct
2 Correct 123 ms 57856 KB Output is correct
3 Correct 169 ms 59052 KB Output is correct
4 Correct 173 ms 59100 KB Output is correct
5 Correct 156 ms 57956 KB Output is correct
6 Correct 173 ms 58636 KB Output is correct
7 Correct 114 ms 58540 KB Output is correct
8 Correct 115 ms 58048 KB Output is correct
9 Correct 124 ms 58420 KB Output is correct
10 Correct 156 ms 58504 KB Output is correct
11 Correct 169 ms 57804 KB Output is correct
12 Correct 155 ms 57856 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -