제출 #811749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
811749		vjudge1	Financial Report (JOI21_financial)	C++17	0 / 100	239 ms	8476 KiB

Main

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 300300;

int dp[N];

struct SlideWin{
    stack < int > L, R, S;

    void add(int x) {
        R.push(max(R.empty() ? 0 : R.top(), x));
        S.push(x);
    }

    void del() {
        if(L.empty()) {
            for(; !S.empty();) {
                L.push(max(L.empty() ? 0 : L.top(), S.top()));
                S.pop();
                R.pop();
            }
        }
        L.pop();
    }

    int get_max() {
        return max(L.empty() ? 0 : L.top(),
                   R.empty() ? 0 : R.top());
    }
};

map < int, SlideWin > mp;

struct node{
    int l, r, mx = 0;
    node *left = NULL, *right = NULL;

    node(int _l, int _r):l(_l), r(_r) {};
};

void check(node *x) {
    if(x->left == NULL) {
        x->left = new node(x->l, (x->l + x->r) / 2);
    }
    if(x->right == NULL) {
        x->right = new node((x->l + x->r) / 2, x->r);
    }
}

void update(int pos, node *x) {
    if(x->l + 1 == x->r) {
        cout << x->l << '\n';
        x->mx = mp[x->l].get_max();
        return;
    }
    check(x);
    pos < x->left->r ?
    update(pos, x->left)  :
    update(pos, x->right) ;

    x->mx = max(x->left->mx, x->right->mx);
}

int get(int r, node *x) {
    if(x->r <= r || x->mx == 0) {
        return x->mx;
    }
    check(x);
    int res = get(r, x->left);
    if(x->right->l < r) {
        res = max(res, get(r, x->right));
    }
    return res;
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, d;
    cin >> n >> d;
    queue < int > q;
    node *root = new node(0, (1<<30));
    for(int i = 1; i <= n; ++ i) {
        cin >> m;
        if(q.size() > d) {
            mp[q.front()].del();
            update(q.front(), root);
            q.pop();
        }
        q.push(m);
        dp[i] = max(get(m, root) + 1, mp[m].get_max());
        mp[m].add(dp[i]);
        update(m, root);
    }
    int mx = 0;
    for(int i = n - d; i <= n; ++ i) {
        mx = max(mx, dp[i]);
    }
    cout << mx;
} 

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:99:21: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |         if(q.size() > d) {
      |            ~~~~~~~~~^~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35