oj.uz

Submission #921440

# Submission time Handle Problem Language Result Execution time Memory
921440 2024-02-03T20:58:54 Z AverageAmogusEnjoyer Financial Report (JOI21_financial) C++17
5 / 100
 339 ms 39764 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
constexpr int nax = 300300;
int n,d;
int a[nax];
int b[nax];
int dp[nax];
int st[4*nax];
multiset<int> s[nax];
void upd(int p,int x,int u=1,int tl=0,int tr=nax) {
    if (tl == tr) {
        st[u] = x;
        return;
    }
    int mid=(tl+tr)/2;
    if (p <= mid) {
        upd(p,x,2*u,tl,mid);
    } else {
        upd(p,x,2*u+1,mid+1,tr);
    }
    st[u] = max(st[2*u],st[2*u+1]);
}
int qry(int l,int r,int u=1,int tl=0,int tr=nax) {
    if (l > r) { return 0; }
    if (l == tl && r == tr) {
        return st[u];
    }
    int mid=(tl+tr)/2;
    return max(qry(l,min(r,mid),2*u,tl,mid),qry(max(mid+1,l),r,2*u+1,mid+1,tr));
}
int main() {
    cin >> n >> d;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b,b+n);
    for (int i=0;i<n;i++) {
        a[i] = lower_bound(b,b+n,a[i])-b;
    }
    int mx = 0;
    for (int i=0;i<n;i++) {
        if (i > d) {
            int w = a[i-d-1];
            auto it = s[w].find(dp[i-d-1]);
            assert(it!=s[w].end());
            s[w].erase(it);
            upd(w,(s[w].empty() ? 0 : *s[w].rbegin()));
        }
        int w = a[i];
        int c = qry(0,w-1)+1;
        s[w].insert(c);
        upd(w,*s[w].rbegin());
        dp[i] = c;
        cmax(mx,dp[i]);
        // cerr << c << endl;
    }
    cout << mx << endl;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19288 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 5 ms 19080 KB Output is correct
4 Correct 5 ms 19036 KB Output is correct
5 Correct 5 ms 19072 KB Output is correct
6 Correct 4 ms 17144 KB Output is correct
7 Correct 5 ms 19072 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 17032 KB Output is correct
11 Correct 5 ms 17244 KB Output is correct
12 Correct 5 ms 19292 KB Output is correct
13 Correct 5 ms 19032 KB Output is correct
14 Correct 5 ms 19036 KB Output is correct
15 Incorrect 4 ms 16988 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19288 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 5 ms 19080 KB Output is correct
4 Correct 5 ms 19036 KB Output is correct
5 Correct 5 ms 19072 KB Output is correct
6 Correct 4 ms 17144 KB Output is correct
7 Correct 5 ms 19072 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 17032 KB Output is correct
11 Correct 5 ms 17244 KB Output is correct
12 Correct 5 ms 19292 KB Output is correct
13 Correct 5 ms 19032 KB Output is correct
14 Correct 5 ms 19036 KB Output is correct
15 Incorrect 4 ms 16988 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19288 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 5 ms 19080 KB Output is correct
4 Correct 5 ms 19036 KB Output is correct
5 Correct 5 ms 19072 KB Output is correct
6 Correct 4 ms 17144 KB Output is correct
7 Correct 5 ms 19072 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 17032 KB Output is correct
11 Correct 5 ms 17244 KB Output is correct
12 Correct 5 ms 19292 KB Output is correct
13 Correct 5 ms 19032 KB Output is correct
14 Correct 5 ms 19036 KB Output is correct
15 Incorrect 4 ms 16988 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 23592 KB Output is correct
2 Incorrect 201 ms 21272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 37792 KB Output is correct
2 Correct 272 ms 36400 KB Output is correct
3 Correct 338 ms 38908 KB Output is correct
4 Correct 339 ms 39060 KB Output is correct
5 Correct 335 ms 39156 KB Output is correct
6 Correct 321 ms 39184 KB Output is correct
7 Correct 174 ms 39508 KB Output is correct
8 Correct 194 ms 39764 KB Output is correct
9 Correct 219 ms 39576 KB Output is correct
10 Correct 251 ms 39464 KB Output is correct
11 Correct 337 ms 39700 KB Output is correct
12 Correct 262 ms 39116 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19288 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 5 ms 19080 KB Output is correct
4 Correct 5 ms 19036 KB Output is correct
5 Correct 5 ms 19072 KB Output is correct
6 Correct 4 ms 17144 KB Output is correct
7 Correct 5 ms 19072 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 16988 KB Output is correct
10 Correct 4 ms 17032 KB Output is correct
11 Correct 5 ms 17244 KB Output is correct
12 Correct 5 ms 19292 KB Output is correct
13 Correct 5 ms 19032 KB Output is correct
14 Correct 5 ms 19036 KB Output is correct
15 Incorrect 4 ms 16988 KB Output isn't correct
16 Halted 0 ms 0 KB -