Submission #1241194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241194		skibidi123	Financial Report (JOI21_financial)	C++20	0 / 100	132 ms	32072 KiB

Main

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

const long INF = (long)1e18;

void init() {
    #define task "main"
    if (fopen(task".INP","r")) {
        freopen(task".INP","r",stdin);
        freopen(task".OUT","w",stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct SegTree {
    int n;
    vector<long> st;
    SegTree(int _n): n(_n), st(4*_n, -INF) {}
    void update(int p, long v) { update(1,1,n,p,v); }
    void update(int node,int l,int r,int p,long v){
        if(l==r){ st[node]=v; return; }
        int m=(l+r)>>1;
        if(p<=m) update(node<<1,l,m,p,v);
        else        update(node<<1|1,m+1,r,p,v);
        st[node]=max(st[node<<1], st[node<<1|1]);
    }
    long query(int i,int j){ return query(1,1,n,i,j); }
    long query(int node,int l,int r,int i,int j){
        if(i>r||j<l) return -INF;
        if(i<=l&&r<=j) return st[node];
        int m=(l+r)>>1;
        return max(query(node<<1,l,m,i,j),
                   query(node<<1|1,m+1,r,i,j));
    }
    // tìm chỉ số nhỏ nhất j in [i..n] sao cho st[j] >= x; nếu không có trả về n+1
    int find_first(int i, long x) { return find_first(1,1,n,i,x); }
    int find_first(int node,int l,int r,int i,long x){
        if(r<i || st[node]<x) return n+1;
        if(l==r) return l;
        int m=(l+r)>>1;
        int t = find_first(node<<1, l, m, i, x);
        if(t<=m) return t;
        return find_first(node<<1|1, m+1, r, i, x);
    }
};

int main(){
    init();

    int N, D;
    cin >> N >> D;
    vector<long> A(N+1);
    for(int i=1;i<=N;i++) cin >> A[i];

    // 1) Tính M[j] = max(A[j-D]..A[j]) với deque
    vector<long> M(N+1, -INF);
    deque<int> dq;
    for(int j=1;j<=N;j++){
        while(!dq.empty() && dq.front() < j-D) dq.pop_front();
        while(!dq.empty() && A[dq.back()] <= A[j]) dq.pop_back();
        dq.push_back(j);
        if(j>=D+1) M[j] = A[dq.front()];
    }

    // 2) Build seg-tree trên M để tìm R[i]
    SegTree stM(N);
    for(int j=D+1;j<=N;j++){
        stM.update(j, M[j]);
    }

    vector<int> R(N+1);
    for(int i=1;i<=N;i++){
        int L = i + D + 1;
        if(L > N){
            R[i] = N;
        } else {
            // tìm j đầu tiên >= L sao cho M[j] >= A[i]+1
            int j = stM.find_first(L, A[i]+1);
            R[i] = (j<=N ? j-1 : N);
        }
    }

    // 3) DP với seg-tree trên dp[]
    SegTree st_dp(N);
    vector<pair<long,int>> order;
    order.reserve(N);
    for(int i=1;i<=N;i++) order.emplace_back(-A[i], i);
    sort(order.begin(), order.end());  // giảm dần A, nếu bằng tăng i

    vector<long> dp(N+1, 0);
    long answer = 0;
    for(auto &pr : order){
        int i = pr.second;
        int l = i+1, r = R[i];
        long best = 0;
        if(l <= r) best = st_dp.query(l,r);
        dp[i] = best + 1;
        st_dp.update(i, dp[i]);
        answer = max(answer, dp[i]);
    }

    cout << answer << "\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void init()':
Main.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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