oj.uz

답안 #684696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684696 2023-01-22T10:51:43 Z vicious Financial Report (JOI21_financial) C++17
5 / 100
 765 ms 209864 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
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;
int a[N],dp[N],ans;
map<int,int> cnt;

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin.exceptions(ios::badbit|ios::failbit);
    cin >> n >> d;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    st = new node(0,1e9);
    for (int i = 1,j=1; i <= n; ++i) {
        dp[i]=1;
        while (i-j>d) {
            --cnt[a[j]];
            if (cnt[a[j]]==0) st->add(a[j],a[j],-st->query(a[j],a[j]));
            ++j;
        }
        dp[i]=st->query(0,a[i]-1)+1;
        ++cnt[a[i]];
        int cur = st->query(a[i],a[i]);
        if (cur<=dp[i]) {
            st->add(a[i],a[i],-cur+dp[i]);
        }
    }
    for (int i = n-1; i >= n-d; --i) {
        chmax(ans, dp[i]+(a[n]>a[i]));
    }
    cout << ans;
    return 0;
}

Compilation message

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

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 5536 KB Output is correct
2 Incorrect 229 ms 5188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 5840 KB Output is correct
2 Correct 227 ms 5596 KB Output is correct
3 Correct 322 ms 8992 KB Output is correct
4 Correct 757 ms 200564 KB Output is correct
5 Correct 683 ms 200588 KB Output is correct
6 Correct 735 ms 200192 KB Output is correct
7 Correct 394 ms 209832 KB Output is correct
8 Correct 378 ms 209864 KB Output is correct
9 Correct 404 ms 199492 KB Output is correct
10 Correct 519 ms 199888 KB Output is correct
11 Correct 765 ms 200588 KB Output is correct
12 Correct 654 ms 200612 KB Output is correct

Subtask #6
0 / 35.0

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