제출 #1274409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274409		G_thang_dizz_lenhi	Financial Report (JOI21_financial)	C++17	0 / 100	204 ms	11676 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 par[N], dp[N], res[N];

void init(){
    for (ii i = 1;i <= n;i++) par[i] = i;
}

ii find_par(ii u){
    return (u == par[u] ? u : par[u] = find_par(par[u]));
}

void connect(ii u, ii v){
    res[v] = max(res[v], dp[u]);
}

ii st[4 * N];

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

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

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

    cout << SOL;

    return 0;
}

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

컴파일 시 표준 에러 (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: 0 / 5
• Subtask 6: 0 / 35