Submission #1274416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274416		G_thang_dizz_lenhi	Financial Report (JOI21_financial)	C++17	5 / 100	243 ms	9364 KiB

Main

#include<bits/stdc++.h>
typedef int ii;
typedef long long ll;

using namespace std;

const string name = "";
const ii MOD = 1e9 + 7;
const ii N = 3e5 + 10;

ii n, d;
ii a[N];

vector<pair<ii, ii>> v;

void INP(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (fopen((name + ".inp").c_str(),"r")){
        freopen((name + ".inp").c_str(),"r",stdin);
        freopen((name + ".out").c_str(),"w",stdout);
    }
    cin >> n >> d;
    for (ii i = 1;i <= n;i++){
        cin >> a[i];
        v.push_back({a[i], i});
    }
}

bool cmp(const pair<ii, ii> a,const pair<ii, ii> b){
    if (a.first != b.first) return a.first < b.first;
    return a.second > b.second;
}

ii dp[N];

ii st[4 * N];

void update(ii id, ii l, ii r, ii pos, ii val){
    if (l > pos || pos > r) return;
    if (l == r){
        st[id] = val;
        return;
    }
    update(id * 2, l, (l + r) / 2, pos, val);
    update(id * 2 + 1, (l + r) / 2 + 1, r, pos, val);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

ii get(ii id,ii l, ii r, ii u, ii v){
    if (u > r || l > v) return 0;
    if (u <= l && r <= v) return st[id];
    return max(get(id * 2, l, (l + r) / 2, u, v), get(id * 2 + 1, (l + r) / 2 + 1, r, u, v));
}

int main(){
    INP();
    sort(v.begin(), v.end(), cmp);
    ii nxt, SOL = 1;
    for (auto x : v){
        nxt = get(1, 1, n, max(1, x.second - d), x.second);
        dp[x.second] = nxt + 1;
        update(1, 1, n, x.second, dp[x.second]);
        SOL = max(SOL, dp[x.second]);
    }

    cout << SOL;

    return 0;
}

//NGT 1600-2000 cf
//1/200 hard quests

Compilation message (stderr)

Main.cpp: In function 'void INP()':
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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