Submission #774466

#	Time	Username	Problem	Language	Result	Execution time	Memory
774466		Sami_Massah	Financial Report (JOI21_financial)	C++17	100 / 100	542 ms	37172 KiB

Main

#include <bits/stdc++.h>
using namespace std;


const int maxn = 3e5 + 12;
int n, d, a[maxn], L[maxn * 4], R[maxn * 4], mx[maxn * 4], mn[maxn * 4];
bool ch[maxn * 4];
vector <int> pos;
map <int, int> mp;
void make_tree(int l, int r, int ind){
    int mid = (l + r) / 2;
    L[ind] = l;
    R[ind] = r;
    mn[ind] = maxn;
    if(l == r)
        return;
    make_tree(l, mid, ind * 2);
    make_tree(mid + 1, r, ind * 2 + 1);
}
void update_tree_mn(int l, int r, int u, int k){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        mn[u] = min(mn[u], k);
        return;
    }
    update_tree_mn(l, r, u * 2, k);
    update_tree_mn(l, r, u * 2 + 1, k);
    mn[u] = min(mn[u * 2], mn[u * 2 + 1]);
}
void push_to(int v){
    int u = v / 2;
    ch[v] = 1;
    mx[v] = mx[u];
}
void update_tree_mx(int l, int r, int u, int k){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        mx[u] = max(mx[u], k);
        return;
    }
    if(ch[u]){
        push_to(u * 2);
        push_to(u * 2 + 1);
        ch[u] = 0;
    }
    update_tree_mx(l, r, u * 2, k);
    update_tree_mx(l, r, u * 2 + 1, k);
    mx[u] = max(mx[u * 2], mx[u * 2 + 1]);
}
void set_tree(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return;
    if(l <= L[u] && R[u] <= r){
        mx[u] = 0;
        ch[u] = 1;
        return;
    }
    if(ch[u]){
        push_to(u * 2);
        push_to(u * 2 + 1);
        ch[u] = 0;
    }
    set_tree(l, r, u * 2);
    set_tree(l, r, u * 2 + 1);
    mx[u] = max(mx[u * 2], mx[u * 2 + 1]);

}
int get_min(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return maxn;
    if(l <= L[u] && R[u] <= r)
        return mn[u];
    return min(get_min(l, r, u * 2), get_min(l, r, u * 2 + 1));
}
int get_max(int l, int r, int u){
    if(r < L[u] || R[u] < l)
        return 0;
    if(l <= L[u] && R[u] <= r)
        return mx[u];
    if(ch[u]){
        push_to(u * 2);
        push_to(u * 2 + 1);
        ch[u] = 0;
    }
    return max(get_max(l, r, u * 2), get_max(l, r, u * 2 + 1));
}
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n >> d;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pos.push_back(a[i]);
        }
    make_tree(0, n, 1);
    sort(pos.begin(), pos.end());
    for(int j = 0; j < pos.size(); j++)
        mp[pos[j]] = j;
    for(int i = 1; i <= n; i++){
        a[i] = mp[a[i]];

    //    cout << a[i] << ' ';
        }
  //  cout << endl;
   // cout << endl;
    int ans = 0;
    for(int i = n; i >= 1; i--){
        int res, loc;
        res = get_max(a[i] + 1, n, 1) + 1;
        update_tree_mx(a[i], a[i], 1, res);
    /*    cout << i << ' ' << res << endl;
        cout << "___" << endl;
        for(int j = a[i] + 1; j <= n; j++)
            cout << get_max(j, j, 1) << ' ';
        cout << endl;*/
        update_tree_mn(i, i, 1, a[i]);
        if(i + d - 1 <= n){
            loc = get_min(i, i + d - 1, 1);
  //          cout << i << "->" << loc << endl;
            set_tree(0, loc - 1, 1);
        }
        ans = max(ans, res);
    //    cout << endl;

    }
    cout << ans << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int j = 0; j < pos.size(); j++)
      |                    ~~^~~~~~~~~~~~

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