Submission #684729

#	Time	Username	Problem	Language	Result	Execution time	Memory
684729		vicious	Financial Report (JOI21_financial)	C++17	5 / 100	998 ms	235376 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,multiset<pi>> q;

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;

void modify(int id, int v) {
    st->add(id,id,-st->query(id,id));
    st->add(id,id,v);
}

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,2e9);
    for (int i = 1,j=1; i <= n; ++i) {
        dp[i]=1;
        while (i-j>d) {
            while (q[a[j]].size() && q[a[j]].rbegin()->si < i-d) {
                q[a[j]].erase(q[a[j]].find(*q[a[j]].rbegin()));
            }        
            if (q[a[j]].size()) modify(a[j],q[a[j]].rbegin()->fi);
            else modify(a[j],0);
            ++j;
        }
        dp[i]=st->query(0,a[i]-1)+1;
        q[a[i]].insert({dp[i],i});
        if (dp[i]>st->query(a[i],a[i])) {
            modify(a[i],dp[i]);
        }
    }
    for (int i = n; i >= n-d; --i) {
        chmax(ans,dp[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