Submission #812188

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
812188	2023-08-07T07:43:50 Z	vjudge1	Financial Report (JOI21_financial)	C++17	Compilation error	0 ms	0 KB

Main

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) {
        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;
    if(n < 20) {
        int n, d;
        cin >> n >> d;
        int arr[n];
        for(int i = 0; i < n; ++ i) {
            cin >> arr[i];
        }
        int ans = 0;
        for(int msk = (1<<n); msk --> 0;) {
            int k = 0, tmp = msk, pr = -1, cr, mx = -1;
            for(; tmp; tmp -= (-tmp&tmp)) {
                cr = lg2(-tmp&tmp);
                if(pr != -1 && cr - pr > d) {
                    k = 0;
                    break;
                }
                if(mx < arr[cr]) {
                    ++ k;
                    mx = arr[cr];
                }
                pr = cr;
            }
            if(pr == n - 1) {
                ans = max(ans, k);
            }
        }
        cout << ans;
        return 0;
    }
    stack < int > st;
    node *root = new node(0, (1<<30));
    for(int i = 1; i <= n; ++ i) {
        cin >> arr[i];
        L[i] = arr[L[i - 1]] < arr[i] ? i : L[i - 1];
        if(i > d + 1) {
            mp[arr[i - d - 1]].del();
            update(arr[i - d - 1], root);
        }
        dp[i] = get(arr[i], root) + 1;
        for(; !st.empty() && arr[st.top()] <= arr[i]; st.pop()) {
            dp[i] = max(dp[i], dp[st.top()] + (arr[st.top()] < arr[i]));
        }
        for(int j = i - 1; j --> (i - d);) {
            for(int cr = j; cr != L[cr] && arr[cr] <= arr[i]; cr = L[cr]) {
                dp[i] = max(dp[i], dp[cr] + (arr[cr] < arr[i]));
            }
        }
        st.push(i);
        mp[arr[i]].add(dp[i]);
        update(arr[i], root);
    }

    int mx = 0;
    for(; !st.empty(); st.pop()) {
        mx = max(mx, dp[st.top()]);
    }
    cout << dp[13] << ' ';
    cout << mx;
} 

Compilation message

Main.cpp:3:18: error: 'NULL' was not declared in this scope
    3 |     node *left = NULL, *right = NULL;
      |                  ^~~~
Main.cpp:1:1: note: 'NULL' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
  +++ |+#include <cstddef>
    1 | struct node{
Main.cpp:3:33: error: 'NULL' was not declared in this scope
    3 |     node *left = NULL, *right = NULL;
      |                                 ^~~~
Main.cpp:3:33: note: 'NULL' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
Main.cpp: In function 'void check(node*)':
Main.cpp:9:19: error: 'NULL' was not declared in this scope
    9 |     if(x->left == NULL) {
      |                   ^~~~
Main.cpp:9:19: note: 'NULL' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
Main.cpp:12:20: error: 'NULL' was not declared in this scope
   12 |     if(x->right == NULL) {
      |                    ^~~~
Main.cpp:12:20: note: 'NULL' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
Main.cpp: In function 'void update(int, node*)':
Main.cpp:19:17: error: 'mp' was not declared in this scope
   19 |         x->mx = mp[x->l].get_max();
      |                 ^~
Main.cpp:27:13: error: 'max' was not declared in this scope
   27 |     x->mx = max(x->left->mx, x->right->mx);
      |             ^~~
Main.cpp: In function 'int get(int, node*)':
Main.cpp:37:15: error: 'max' was not declared in this scope
   37 |         res = max(res, get(r, x->right));
      |               ^~~
Main.cpp: At global scope:
Main.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:47:5: error: 'ios_base' has not been declared
   47 |     ios_base::sync_with_stdio(0);
      |     ^~~~~~~~
Main.cpp:48:5: error: 'cin' was not declared in this scope
   48 |     cin.tie(0);
      |     ^~~
Main.cpp:63:22: error: 'lg2' was not declared in this scope
   63 |                 cr = lg2(-tmp&tmp);
      |                      ^~~
Main.cpp:75:23: error: 'max' was not declared in this scope; did you mean 'mx'?
   75 |                 ans = max(ans, k);
      |                       ^~~
      |                       mx
Main.cpp:78:9: error: 'cout' was not declared in this scope
   78 |         cout << ans;
      |         ^~~~
Main.cpp:81:5: error: 'stack' was not declared in this scope
   81 |     stack < int > st;
      |     ^~~~~
Main.cpp:81:13: error: expected primary-expression before 'int'
   81 |     stack < int > st;
      |             ^~~
Main.cpp:84:16: error: 'arr' was not declared in this scope
   84 |         cin >> arr[i];
      |                ^~~
Main.cpp:85:9: error: 'L' was not declared in this scope
   85 |         L[i] = arr[L[i - 1]] < arr[i] ? i : L[i - 1];
      |         ^
Main.cpp:87:13: error: 'mp' was not declared in this scope; did you mean 'm'?
   87 |             mp[arr[i - d - 1]].del();
      |             ^~
      |             m
Main.cpp:90:9: error: 'dp' was not declared in this scope; did you mean 'd'?
   90 |         dp[i] = get(arr[i], root) + 1;
      |         ^~
      |         d
Main.cpp:91:16: error: 'st' was not declared in this scope; did you mean 'std'?
   91 |         for(; !st.empty() && arr[st.top()] <= arr[i]; st.pop()) {
      |                ^~
      |                std
Main.cpp:92:21: error: 'max' was not declared in this scope
   92 |             dp[i] = max(dp[i], dp[st.top()] + (arr[st.top()] < arr[i]));
      |                     ^~~
Main.cpp:96:25: error: 'max' was not declared in this scope
   96 |                 dp[i] = max(dp[i], dp[cr] + (arr[cr] < arr[i]));
      |                         ^~~
Main.cpp:99:9: error: 'st' was not declared in this scope; did you mean 'std'?
   99 |         st.push(i);
      |         ^~
      |         std
Main.cpp:100:9: error: 'mp' was not declared in this scope; did you mean 'm'?
  100 |         mp[arr[i]].add(dp[i]);
      |         ^~
      |         m
Main.cpp:105:12: error: 'st' was not declared in this scope; did you mean 'std'?
  105 |     for(; !st.empty(); st.pop()) {
      |            ^~
      |            std
Main.cpp:106:22: error: 'dp' was not declared in this scope; did you mean 'd'?
  106 |         mx = max(mx, dp[st.top()]);
      |                      ^~
      |                      d
Main.cpp:106:14: error: 'max' was not declared in this scope; did you mean 'mx'?
  106 |         mx = max(mx, dp[st.top()]);
      |              ^~~
      |              mx
Main.cpp:108:5: error: 'cout' was not declared in this scope
  108 |     cout << dp[13] << ' ';
      |     ^~~~
Main.cpp:108:13: error: 'dp' was not declared in this scope; did you mean 'd'?
  108 |     cout << dp[13] << ' ';
      |             ^~
      |             d
Main.cpp:50:12: warning: unused variable 'm' [-Wunused-variable]
   50 |     int n, m, d;
      |            ^