oj.uz

Submission #953201

# Submission time Handle Problem Language Result Execution time Memory
953201 2024-03-25T17:03:27 Z happy_node Financial Report (JOI21_financial) C++17
5 / 100
 523 ms 29132 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX=3e5+5;

int dp[MX], R[MX];

struct segtree {
        pair<int,int> t[4*MX];

        void update(int v, int l, int r, int pos, pair<int,int> val) {
                if(l>pos||r<pos) return;
                if(l==r) {
                        t[v]=val;
                        return;
                }
                int mid=(l+r)>>1;
                update(v*2+0,l,mid+0,pos,val);
                update(v*2+1,mid+1,r,pos,val);
                t[v]=max(t[v*2+0],t[v*2+1]);
        }

        pair<int,int> query(int v, int l, int r, int ql, int qr) {
                if(qr<l||r<ql) return make_pair(-1,-1);
                if(ql<=l&&qr>=r) return t[v];
                int mid=(l+r)>>1;
                return max(query(v*2+0,l,mid+0,ql,qr),
                        query(v*2+1,mid+1,r,ql,qr));
        }

        void reset() {
                for(int i=0;i<4*MX;i++) {
                        t[i]=make_pair(-1,-1);
                }
        }
} st;

struct segtreeMin {
        int t[4*MX];

        void update(int v, int l, int r, int pos, int val) {
                if(l>pos||r<pos) return;
                if(l==r) {
                        t[v]=val;
                        return;
                }
                int mid=(l+r)>>1;
                update(v*2+0,l,mid+0,pos,val);
                update(v*2+1,mid+1,r,pos,val);
                t[v]=min(t[v*2+0],t[v*2+1]);
        }

        int query(int v, int l, int r, int ql, int qr) {
                if(qr<l||r<ql) return 1e9;
                if(ql<=l&&qr>=r) return t[v];
                int mid=(l+r)>>1;
                return min(query(v*2+0,l,mid+0,ql,qr),
                        query(v*2+1,mid+1,r,ql,qr));
        }

        void reset() {
                for(int i=0;i<4*MX;i++) {
                        t[i]=1e9;
                }
        }
} tt;

int _N;

int getPos(int L, int R, int x) {
        int l=L,r=R,res=-1;
        while(l<=r) {
                int mid=(l+r)>>1;
                if(tt.query(1,0,_N-1,mid,R)<=x) {
                        res=mid;
                        l=mid+1;
                } else {
                        r=mid-1;
                }
        }
        // cout<<L<<" "<<R<<" "<<x<<" "<<res<<'\n';
        return res;
}

int rev[MX];

int solveChallange(int N, int D, std::vector<int> H) { 
        _N=N;
        st.reset(); 
        tt.reset();

        vector<pair<int,int>> ord;
        vector<int> P(N);

        for(int i=0;i<N;i++) {
                ord.push_back({H[i],-i});
        }
        sort(ord.begin(),ord.end());
        int cnt=1;
        for(auto [h,id]:ord) {
                id=-id;
                P[id]=cnt++;
                rev[P[id]]=id;
        }

        for(int l=0;l<N;l++) tt.update(1,0,N-1,l,P[l]);

        for(int l=N-1;l>=0;l--) {
                int p=getPos(l,min(N-1,l+D),P[l]);
                if(p==-1)
                        R[l]=min(N-1,l+D);
                else
                        R[l]=max(min(N-1,l+D),R[rev[p]]);
        }

        for(int i=0;i<N;i++) {
                while(true) {
                        auto [V,p]=st.query(1,1,N,1,P[i]-1);
                        if(p==-1) break;
                        if(R[p]<i) {
                                st.update(1,1,N,P[p],make_pair(-1,-1));
                                continue;
                        }
                        dp[i]=V+1;
                        break;
                }

                dp[i]=max(dp[i],1);
                st.update(1,1,N,P[i],make_pair(dp[i],i));
        }

        return *max_element(dp,dp+N);
}


int main() {
        int N, D;
        std::vector<int> H;
        scanf("%d %d", &N, &D);
        H.resize(N);
        for (auto &elem : H) {
        scanf("%d", &elem);
        }
        int answer = solveChallange(N, D, H);
        printf("%d\n", answer);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         scanf("%d %d", &N, &D);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         scanf("%d", &elem);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 3 ms 16832 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16864 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 3 ms 16728 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Incorrect 3 ms 16732 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 3 ms 16832 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16864 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 3 ms 16728 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Incorrect 3 ms 16732 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 3 ms 16832 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16864 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 3 ms 16728 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Incorrect 3 ms 16732 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 26060 KB Output is correct
2 Correct 243 ms 29120 KB Output is correct
3 Incorrect 280 ms 27960 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 26044 KB Output is correct
2 Correct 437 ms 27328 KB Output is correct
3 Correct 449 ms 28868 KB Output is correct
4 Correct 449 ms 27832 KB Output is correct
5 Correct 437 ms 28724 KB Output is correct
6 Correct 489 ms 27572 KB Output is correct
7 Correct 454 ms 28608 KB Output is correct
8 Correct 380 ms 28100 KB Output is correct
9 Correct 477 ms 28608 KB Output is correct
10 Correct 523 ms 29132 KB Output is correct
11 Correct 439 ms 27816 KB Output is correct
12 Correct 437 ms 28444 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 3 ms 16832 KB Output is correct
5 Correct 3 ms 16732 KB Output is correct
6 Correct 3 ms 16732 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 4 ms 16732 KB Output is correct
9 Correct 3 ms 16732 KB Output is correct
10 Correct 3 ms 16732 KB Output is correct
11 Correct 3 ms 16732 KB Output is correct
12 Correct 3 ms 16864 KB Output is correct
13 Correct 3 ms 16732 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 3 ms 16728 KB Output is correct
16 Correct 3 ms 16732 KB Output is correct
17 Correct 3 ms 16732 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 3 ms 16732 KB Output is correct
21 Incorrect 3 ms 16732 KB Output isn't correct
22 Halted 0 ms 0 KB -