제출 #1099231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099231		ducdev	Global Warming (CEOI18_glo)	C++14	10 / 100	63 ms	8860 KiB

glo

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

#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef pair<int, int> ii;

const int MAX_N = 1e6;
const int MOD = (int)1e9 + 7;

template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x >= y) return false;
        x = y;
        return true;
    };
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x <= y) return false;
        x = y;
        return true;
    };

int n;
ll a[MAX_N + 5], x;

struct FenwickTree {
    int n;
    vector<int> bit;

    void update(int pos, int val) {
        for (; pos <= n; pos += pos & (-pos))
            maximize(bit[pos], val);
    };

    int get(int pos) {
        int ret = 0;
        for (; pos > 0; pos -= pos & (-pos))
            maximize(ret, bit[pos]);
        return ret;
    };

    FenwickTree(int n) : n(n) {
        bit.assign(n + 5, 0);
    };
};

namespace SUBTASK_1 {
    const int N = MAX_N;

    ll c[N + 5];
    int dp[N + 5][5];

    void Solve() {
//        for (int i = 1; i <= n; i++) c[i] = a[i];
//        vector<ll> v;
//        for (int i = 1; i <= n; i++) v.push_back(a[i]), v.push_back(a[i] + x), v.push_back(a[i] - x);
//        sort(all(v));
//        v.resize(unique(all(v)) - v.begin());
//
//        for (int i = 1; i <= n; i++) c[i] = lower_bound(all(v), c[i]) - v.begin() + 1;

        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 4; j++) dp[i][j] = 1;
            for (int j = 1; j < i; j++) {
                if(a[i] + x > a[j]) {
                    maximize(dp[i][1], dp[j][0] + 1);
                }
                if (a[i] - x > a[j]) {
                    maximize(dp[i][2], dp[j][0] + 1);
                }
                if (a[i] > a[j]) {
                    maximize(dp[i][0], dp[j][0] + 1);
                    maximize(dp[i][1], dp[j][1] + 1);
                    maximize(dp[i][2], dp[j][2] + 1);
                };
                if (a[i] > a[j] + x) {
                    maximize(dp[i][3], dp[i][1] + 1);
                };
                if (a[i] > a[j] - x) {
                    maximize(dp[i][3], dp[i][2] + 1);
                }
            }
            res = max({res, dp[i][0], dp[i][1], dp[i][2], dp[i][3]});
        };
        cout << res << '\n';
    };
};

namespace SUBTASK_2 {
    const int N = MAX_N;

    ll c[N + 5];

    void Solve() {
        for (int i = 1; i <= n; i++) c[i] = a[i];
        vector<ll> v(c + 1, c + n + 1);
        sort(all(v));
        v.resize(unique(all(v)) - v.begin());

        for (int i = 1; i <= n; i++) c[i] = lower_bound(all(v), c[i]) - v.begin() + 1;

        int res = 0;
        FenwickTree bit(n);
        for (int i = 1; i <= n; i++) {
            int dp = bit.get(c[i] - 1);
            bit.update(c[i], dp + 1);
            maximize(res, dp + 1);
        };

        cout << res << '\n';
    };
};

void checkAns() {
    #define TASK "GLO"

    system("g++ gentest." TASK ".cpp -o gentest." TASK " -std=c++14 -O2 -Wall -Wextra");

    const int TEST_CASE = 3;
    int tc = 0;
    while (tc < TEST_CASE) {
        system("gentest." TASK " > " TASK ".INP");

        freopen(TASK ".INP", "r", stdin);
        freopen(TASK ".OUT", "w", stdout);

        int n; cin >> n;
        cerr << n << '\n';

        assert(true);

        cerr << ++tc << ": PASSED\n";
//        cerr << SUBTASK_1::ans << ' ' << SUBTASK_2::ans << '\n';
    }
    exit(0);
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    };

    if (x == 0)
        return SUBTASK_2::Solve(), 0;
    if (n <= 1000) return SUBTASK_1::Solve(),0;
    cout << n;
};

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

glo.cpp: In function 'void checkAns()':
glo.cpp:120:11: warning: ignoring return value of 'int system(const char*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     system("g++ gentest." TASK ".cpp -o gentest." TASK " -std=c++14 -O2 -Wall -Wextra");
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:125:15: warning: ignoring return value of 'int system(const char*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         system("gentest." TASK " > " TASK ".INP");
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(TASK ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(TASK ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25