oj.uz

답안 #881891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881891 2023-12-02T07:59:54 Z deadeye0 Financial Report (JOI21_financial) C++17
5 / 100
 567 ms 53880 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
#define ar array
#define pb push_back
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
typedef vector<int> vi;
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N = 300010;
int n, d, ans;
int a[N], dp[N];
map<pi, int> active;

struct node {
    node *l, *r;
    int val, s, m, e, lazyadd;
    bool upd;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), upd(false), l(NULL), r(NULL) {
        if (s != e) l = new node(s, m), r = new node(m+1, e);
    }
    int value() { 
        if (upd) {
            val = lazyadd;
            upd = false;
            if (s == e) return val;
            l->lazyadd = lazyadd;
            r->lazyadd = lazyadd;
            r->upd = true, l->upd = true;
        }
        return val;
    }
    void set(int x, int y, int v) {
        if (s == x && e == y) lazyadd = v, upd = true;
        else {
            if (x > m) r->set(x, y, v);
            else if (y <= m) l->set(x, y, v);
            else l->set(x, m, v), r->set(m+1, y, v);
            val = max(l->value(), r->value()); 
        }
    }
    int query(int x, int y) {
        value();
        if (s == x && e == y) return value();
        if (x > m) return r->query(x, y);
        if (y <= m) return l->query(x, y);
        return max(l->query(x, m),r->query(m+1, y)); 
    }
} *st;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin.exceptions(ios::badbit|ios::failbit);
    cin >> n >> d;
    vector<int> temp(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        temp[i] = a[i];
    }
    sort(temp.begin(), temp.end());
    temp.resize(unique(temp.begin(), temp.end()) - temp.begin());
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin();
        dp[a[i]] = 1;
    }
    st = new node(0, n);
    for (int i = 0; i < n; ++i) {
        if (i - d - 1 >= 0) {
            --active[{a[i - d - 1], dp[i - d - 1]}];
            if (active[{a[i - d - 1], dp[i - d - 1]}] == 0) {
                st->set(a[i - d - 1], a[i - d - 1], 0);
            } 
        }
        if (a[i] == 0) dp[i] = 1;
        else dp[i] = st->query(0, a[i] - 1) + 1;
        if (st->query(a[i], a[i]) < dp[i]) {
            st->set(a[i], a[i], dp[i]);
        }
        ++active[{a[i], dp[i]}];
        chmax(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

Compilation message

Main.cpp: In constructor 'node::node(int, int)':
Main.cpp:24:20: warning: 'node::e' will be initialized after [-Wreorder]
   24 |     int val, s, m, e, lazyadd;
      |                    ^
Main.cpp:24:17: warning:   'int node::m' [-Wreorder]
   24 |     int val, s, m, e, lazyadd;
      |                 ^
Main.cpp:26:5: warning:   when initialized here [-Wreorder]
   26 |     node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), upd(false), l(NULL), r(NULL) {
      |     ^~~~
Main.cpp:24:17: warning: 'node::m' will be initialized after [-Wreorder]
   24 |     int val, s, m, e, lazyadd;
      |                 ^
Main.cpp:24:9: warning:   'int node::val' [-Wreorder]
   24 |     int val, s, m, e, lazyadd;
      |         ^~~
Main.cpp:26:5: warning:   when initialized here [-Wreorder]
   26 |     node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), upd(false), l(NULL), r(NULL) {
      |     ^~~~
Main.cpp:25:10: warning: 'node::upd' will be initialized after [-Wreorder]
   25 |     bool upd;
      |          ^~~
Main.cpp:23:11: warning:   'node* node::l' [-Wreorder]
   23 |     node *l, *r;
      |           ^
Main.cpp:26:5: warning:   when initialized here [-Wreorder]
   26 |     node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), upd(false), l(NULL), r(NULL) {
      |     ^~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 32084 KB Output is correct
2 Incorrect 134 ms 34480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 32080 KB Output is correct
2 Correct 105 ms 35152 KB Output is correct
3 Correct 303 ms 50156 KB Output is correct
4 Correct 567 ms 53840 KB Output is correct
5 Correct 437 ms 53880 KB Output is correct
6 Correct 542 ms 53860 KB Output is correct
7 Correct 191 ms 53764 KB Output is correct
8 Correct 193 ms 53640 KB Output is correct
9 Correct 195 ms 53452 KB Output is correct
10 Correct 298 ms 53584 KB Output is correct
11 Correct 531 ms 53848 KB Output is correct
12 Correct 436 ms 53840 KB Output is correct

Subtask #6
0 / 35.0

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