Submission #528152

#	Time	Username	Problem	Language	Result	Execution time	Memory
528152		AdamGS	Financial Report (JOI21_financial)	C++17	5 / 100	169 ms	16176 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define pb push_back
#define st first
#define nd second
const int LIM=3e5+7;
int tr[4*LIM], tr2[4*LIM], N=1;
pair<int,int>T[LIM];
void upd1(int v, int x) {
    v+=N;
    while(v) {
        tr[v]=min(tr[v], x);
        v/=2;
    }
}
int cnt1(int l, int r) {
    l+=N; r+=N;
    int ans=min(tr[l], tr[r]);
    while(l/2!=r/2) {
        if(l%2==0) ans=min(ans, tr[l+1]);
        if(r%2==1) ans=min(ans, tr[r-1]);
        l/=2; r/=2;
    }
    return ans;
}
void upd2(int v, int x) {
    v+=N;
    while(v) {
        tr2[v]=max(tr2[v], x);
        v/=2;
    }
}
int cnt2(int l, int r) {
    l+=N; r+=N;
    int ans=max(tr2[l], tr2[r]);
    while(l/2!=r/2) {
        if(l%2==0) ans=max(ans, tr2[l+1]);
        if(r%2==1) ans=max(ans, tr2[r-1]);
        l/=2; r/=2;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, d;
    cin >> n >> d;
    while(N<n) N*=2;
    rep(i, N) tr[N+i]=i;
    for(int i=N-1; i; --i) tr[i]=min(tr[2*i], tr[2*i+1]);
    rep(i, n) {
        cin >> T[i].st;
        T[i].nd=i;
    }
    sort(T, T+n);
    int ans=0;
    vector<pair<int,pair<int,int>>>V;
    rep(i, n) {
        if(i && T[i].st!=T[i-1].st) {
            for(auto j : V) {
                upd1(j.st, j.nd.st);
                upd2(j.st, j.nd.nd);
            }
            V.clear();
        }
        int p=cnt1(max(T[i].nd-d, 0), T[i].nd);
        int x=cnt2(p, T[i].nd)+1;
        ans=max(ans, x);
        V.pb({T[i].nd, {p, x}});
    }
    cout << ans << '\n';
}

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