oj.uz

답안 #527076

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527076 2022-02-17T00:40:35 Z jalsol Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++11
8 / 100
 633 ms 36612 KB 
#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 1e6 + 5;

int n, nq;
int a[maxN];
int ql[maxN];
int qr[maxN];
int qk[maxN];

struct Sub1 {
    bool test(int l, int r, int k) {
        For (i, l, r) {
            For (j, i + 1, r) {
                if (a[i] > a[j] && a[i] + a[j] > k) {
                    return false;
                }
            }
        }

        return true;
    }

    void solve() {
        For (i, 1, nq) {
            cout << test(ql[i], qr[i], qk[i]) << '\n';
        }
    }
};

struct Sub2 {
    bool test(int l, int r, int k) {
        set<int> st;

        For (i, l, r) {
            auto it = st.upper_bound(a[i]);
            if (it != st.end()) {
                if (a[i] + *it > k) return false;
            }
            st.insert(a[i]);
        }

        return true;
    }

    void solve() {
        For (i, 1, nq) {
            cout << test(ql[i], qr[i], qk[i]) << '\n';
        }
    }
};

struct Sub3 {
    vector<pair<int, int>> seg;

    bool test(int l, int r) {
        auto it = lower_bound(all(seg), make_pair(l, -1));
        return r <= it->se;
    }

    void solve() {
        seg.reserve(n);

        For (i, 1, n) {
            int j = i;

            while (j + 1 <= n && a[j] <= a[j + 1]) {
                ++j;
            }

            seg.emplace_back(i, j);
            i = j;
        }

        For (i, 1, nq) {
            cout << test(ql[i], qr[i]) << '\n';
        }
    }
};

signed main() {
    cin >> n >> nq;
    For (i, 1, n) cin >> a[i];

    For (i, 1, nq) {
        cin >> ql[i] >> qr[i] >> qk[i];
    }

    bool sub3 = true;
    {
        int mn = *min_element(a + 1, a + n + 1);
        For (i, 1, nq) {
            sub3 &= (qk[i] < mn);
        }
    }

#define SUB(x) \
    Sub##x* sol = new Sub##x{}; \
    sol->solve(); delete sol

    if (n <= 500 && nq <= 500) {
        SUB(1);
    } else if (n <= 5000 && nq <= 5000) {
        SUB(2);
    } else if (sub3) {
        SUB(3);
    } else {
        assert(false);
    }
}

/*

*/

Compilation message

sortbooks.cpp: In constructor '__Init__::__Init__()':
sortbooks.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 24 ms 324 KB Output is correct
9 Correct 11 ms 360 KB Output is correct
10 Correct 9 ms 332 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 24 ms 324 KB Output is correct
9 Correct 11 ms 360 KB Output is correct
10 Correct 9 ms 332 KB Output is correct
11 Incorrect 5 ms 460 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 633 ms 36612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 5612 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 24 ms 324 KB Output is correct
9 Correct 11 ms 360 KB Output is correct
10 Correct 9 ms 332 KB Output is correct
11 Incorrect 5 ms 460 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 24 ms 324 KB Output is correct
9 Correct 11 ms 360 KB Output is correct
10 Correct 9 ms 332 KB Output is correct
11 Incorrect 5 ms 460 KB Output isn't correct
12 Halted 0 ms 0 KB -