Submission #684696

#	Time	Username	Problem	Language	Result	Execution time	Memory
684696		vicious	Financial Report (JOI21_financial)	C++17	5 / 100	765 ms	209864 KiB

Main

#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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35