Submission #533774

#	Time	Username	Problem	Language	Result	Execution time	Memory
533774		someone	Financial Report (JOI21_financial)	C++14	100 / 100	535 ms	15200 KiB

Main

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

struct Val {
    int val, i;
};
 
const int M = 1 << 19, N = 2 * M, T = 3;

Val a[M];
deque<int> mini;
int n, d, ans = 0, maxi[N], len[M], tag_a[N], tag_b[N];

inline void updNode(int i, int a, int b) {
    tag_a[i] *= a;
    tag_b[i] = tag_b[i] * a + b;
    maxi[i] = maxi[i] * a + b;
}

int update(int i, int deb, int fin, int a, int b, int d = 0, int f = M) {
    if(deb <= d && f <= fin) {
        updNode(i, a, b);
        return maxi[i];
    }
    if(f <= deb || fin <= d)
        return 0;
        
    updNode(i*2, tag_a[i], tag_b[i]);
    updNode(i*2+1, tag_a[i], tag_b[i]);
    
    tag_a[i] = 1;
    tag_b[i] = 0;
    
    int med = (d + f) >> 1,
        ans = max(update(i*2, deb, fin, a, b, d, med), update(i*2+1, deb, fin, a, b, med, f));
        
    maxi[i] = max(maxi[i*2], maxi[i*2+1]);
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> d;
    for(int i = 0; i < n; i++)
        cin >> a[i].val;
    for(int i = 0; i < n; i++)
        a[i].i = i;
    
    sort(a, a + n,
    [](Val v1, Val v2) {
        return v1.val < v2.val;
    });
    
    int pre = a[0].val;
    a[0].val = 0;
    for(int i = 1; i < n; i++)
        if(a[i].val == pre) {
            a[i].val = a[i-1].val;
        } else {
            pre = a[i].val;
            a[i].val = a[i-1].val+1;
        }
    
    sort(a, a + n,
    [](Val v1, Val v2) {
        return v1.i < v2.i;
    });
    
    for(int i = 0, j = -d; i < n; i++, j++) {
        len[i] = max(update(1, 0, a[i].val, 1, 0)+1, update(1, a[i].val, a[i].val+1, 1, 0));
        ans = max(ans, len[i]);
        while(!mini.empty() && mini.back() > a[i].val)
            mini.pop_back();
        mini.push_back(a[i].val);
        if(j >= 0) {
            if(a[j].val == mini[0])
                mini.pop_front();
            update(1, 0, mini[0], 0, 0);
        }
        update(1, a[i].val, a[i].val+1, 0, len[i]);
    }
    cout << ans;
}

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