oj.uz

Submission #953200

# Submission time Handle Problem Language Result Execution time Memory
953200 2024-03-25T17:01:50 Z happy_node Financial Report (JOI21_financial) C++17
28 / 100
 4000 ms 34292 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=L;
        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;
                }
        }
        return res;
}

bool valid[1000][1000];

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--) {
                // cari posisi terkanan sehingga min nya itu udah <= x
                int p=getPos(l,min(N-1,l+D),P[l]);
                R[l]=max(R[min(N-1,l+D)],R[p]);
        }

        for(int l=0;l<N;l++) {
                int lst=l; // last yang <= H[l]
                valid[l][l]=1;
                for(int r=l+1;r<N;r++) {
                        if(r-lst<=D) valid[l][r]=valid[l][lst];
                        if(H[r]<=H[l]) lst=r;
                }
                for(int r=N-1;r>l;r--) {
                        if(valid[l][r]) {
                                R[l]=r;
                                break;
                        }
                }
                for(int r=l;r<=R[l];r++) {
                        assert(valid[l][r]);
                }
        }

        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:155:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         scanf("%d %d", &N, &D);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         scanf("%d", &elem);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 16848 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 4 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 5 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 16732 KB Output is correct
13 Correct 3 ms 16728 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 4 ms 16732 KB Output is correct
16 Correct 3 ms 16728 KB Output is correct
17 Correct 5 ms 16732 KB Output is correct
18 Correct 4 ms 17140 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 4 ms 16732 KB Output is correct
21 Correct 3 ms 16728 KB Output is correct
22 Correct 4 ms 16732 KB Output is correct
23 Correct 4 ms 16732 KB Output is correct
24 Correct 3 ms 16732 KB Output is correct
25 Correct 5 ms 16732 KB Output is correct
26 Correct 4 ms 16732 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 16848 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 4 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 5 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 16732 KB Output is correct
13 Correct 3 ms 16728 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 4 ms 16732 KB Output is correct
16 Correct 3 ms 16728 KB Output is correct
17 Correct 5 ms 16732 KB Output is correct
18 Correct 4 ms 17140 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 4 ms 16732 KB Output is correct
21 Correct 3 ms 16728 KB Output is correct
22 Correct 4 ms 16732 KB Output is correct
23 Correct 4 ms 16732 KB Output is correct
24 Correct 3 ms 16732 KB Output is correct
25 Correct 5 ms 16732 KB Output is correct
26 Correct 4 ms 16732 KB Output is correct
27 Correct 4 ms 16732 KB Output is correct
28 Correct 4 ms 16732 KB Output is correct
29 Correct 4 ms 16732 KB Output is correct
30 Correct 4 ms 16732 KB Output is correct
31 Correct 4 ms 16928 KB Output is correct
32 Correct 4 ms 16732 KB Output is correct
33 Correct 4 ms 16732 KB Output is correct
34 Correct 4 ms 16732 KB Output is correct
35 Correct 4 ms 16728 KB Output is correct
36 Correct 4 ms 16732 KB Output is correct
37 Correct 4 ms 16728 KB Output is correct
38 Correct 3 ms 16732 KB Output is correct
39 Correct 4 ms 16728 KB Output is correct
40 Correct 4 ms 16732 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 16848 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 4 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 5 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 16732 KB Output is correct
13 Correct 3 ms 16728 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 4 ms 16732 KB Output is correct
16 Correct 3 ms 16728 KB Output is correct
17 Correct 5 ms 16732 KB Output is correct
18 Correct 4 ms 17140 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 4 ms 16732 KB Output is correct
21 Correct 3 ms 16728 KB Output is correct
22 Correct 4 ms 16732 KB Output is correct
23 Correct 4 ms 16732 KB Output is correct
24 Correct 3 ms 16732 KB Output is correct
25 Correct 5 ms 16732 KB Output is correct
26 Correct 4 ms 16732 KB Output is correct
27 Correct 4 ms 16732 KB Output is correct
28 Correct 4 ms 16732 KB Output is correct
29 Correct 4 ms 16732 KB Output is correct
30 Correct 4 ms 16732 KB Output is correct
31 Correct 4 ms 16928 KB Output is correct
32 Correct 4 ms 16732 KB Output is correct
33 Correct 4 ms 16732 KB Output is correct
34 Correct 4 ms 16732 KB Output is correct
35 Correct 4 ms 16728 KB Output is correct
36 Correct 4 ms 16732 KB Output is correct
37 Correct 4 ms 16728 KB Output is correct
38 Correct 3 ms 16732 KB Output is correct
39 Correct 4 ms 16728 KB Output is correct
40 Correct 4 ms 16732 KB Output is correct
41 Runtime error 46 ms 34292 KB Execution killed with signal 6
42 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 28864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4093 ms 28964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 16848 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 4 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 5 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 16732 KB Output is correct
13 Correct 3 ms 16728 KB Output is correct
14 Correct 4 ms 16732 KB Output is correct
15 Correct 4 ms 16732 KB Output is correct
16 Correct 3 ms 16728 KB Output is correct
17 Correct 5 ms 16732 KB Output is correct
18 Correct 4 ms 17140 KB Output is correct
19 Correct 3 ms 16732 KB Output is correct
20 Correct 4 ms 16732 KB Output is correct
21 Correct 3 ms 16728 KB Output is correct
22 Correct 4 ms 16732 KB Output is correct
23 Correct 4 ms 16732 KB Output is correct
24 Correct 3 ms 16732 KB Output is correct
25 Correct 5 ms 16732 KB Output is correct
26 Correct 4 ms 16732 KB Output is correct
27 Correct 4 ms 16732 KB Output is correct
28 Correct 4 ms 16732 KB Output is correct
29 Correct 4 ms 16732 KB Output is correct
30 Correct 4 ms 16732 KB Output is correct
31 Correct 4 ms 16928 KB Output is correct
32 Correct 4 ms 16732 KB Output is correct
33 Correct 4 ms 16732 KB Output is correct
34 Correct 4 ms 16732 KB Output is correct
35 Correct 4 ms 16728 KB Output is correct
36 Correct 4 ms 16732 KB Output is correct
37 Correct 4 ms 16728 KB Output is correct
38 Correct 3 ms 16732 KB Output is correct
39 Correct 4 ms 16728 KB Output is correct
40 Correct 4 ms 16732 KB Output is correct
41 Runtime error 46 ms 34292 KB Execution killed with signal 6
42 Halted 0 ms 0 KB -