제출 #1337650

#제출 시각아이디문제언어결과실행 시간메모리
1337650Rafael_AugustoGlobal Warming (CEOI18_glo)C++20
100 / 100
478 ms49736 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define f first
#define s second
#define get(i, v) get<i>(v)
#define all(v) v.begin(), v.end()
#define dbg(v) cerr << #v << " = " << v << "\n"
#define fall(i, s, n) for(int i=s; i<n; i++)
#define rfall(i, s, n) for(int i=s; i>=n; i--)

typedef pair<int, int> pii;
typedef tuple<int, int, int> trio;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setIO(string name){
    freopen((name+".in").c_str(), "r", stdin);
    freopen((name+".out").c_str(), "w", stdout);
}

const int MAXN = 4e5+7;

int seg0[4*MAXN], seg1[4*MAXN];
int dp[MAXN][2];

void upd(int seg[], int i, int l, int r, int x, int v){
    int m = (l+r)/2;

    if(l == r) seg[i]=v;
    else if(x < l || r < x) return;
    else{
        if(x <= m) upd(seg, 2*i+1, l, m, x, v);
        else upd(seg, 2*i+2, m+1, r, x, v);

        seg[i] = max(seg[2*i+1], seg[2*i+2]);
    }
}

int qry(int seg[], int i, int l, int r, int x, int y){
    int m = (l+r)/2;

    if(r < x || y < l) return 0;
    else if(x <= l && r <= y) return seg[i];
    else return max(qry(seg, 2*i+1, l, m, x, y), qry(seg, 2*i+2, m+1, r, x, y));
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);

    int n, x; cin >> n >> x;

    int a[n];

    fall(i, 0, n) cin >> a[i];

    map<int, int> mp;

    auto comp = [&](){
        vector<int> cmp;

        fall(i, 0, n) cmp.pb(a[i]), cmp.pb(a[i]+x);

        sort(all(cmp));

        rfall(i, 2*n-1, 0) mp[cmp[i]]=i+1;
    };

    comp();

    fall(i, 0, n){
        int k = mp[a[i]];

        dp[k][0] = max(dp[k][0], qry(seg0, 0, 1, MAXN-1, 1, k-1)+1);

        int j = mp[a[i]+x];

        dp[j][1] = max({dp[j][1], qry(seg1, 0, 1, MAXN-1, 1, j-1)+1, qry(seg0, 0, 1, MAXN-1, 1, j-1)+1});

        upd(seg0, 0, 1, MAXN-1, k, dp[k][0]);
        upd(seg1, 0, 1, MAXN-1, j, dp[j][1]);
    }

    cout << max(qry(seg0, 0, 1, MAXN-1, 1, MAXN-1), qry(seg1, 0, 1, MAXN-1, 1, MAXN-1)) << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'void setIO(std::string)':
glo.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...