oj.uz

답안 #836260

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
836260 2023-08-24T09:20:15 Z green_gold_dog Fire (JOI20_ho_t5) C++17
7 / 100
 150 ms 67396 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

struct sparce_table {
        vector<vector<pair<ll, ll>>> arr;
        vector<ll> lg;
        sparce_table(vector<ll> a) {
                lg.push_back(0);
                while (lg.size() <= a.size()) {
                        lg.push_back(lg.back());
                        if ((1 << (lg.back() + 1)) == lg.size() - 1) {
                                lg.back()++;
                        }
                }
                arr.resize(lg.back() + 1, vector<pair<ll, ll>>(a.size()));
                for (ll i = 0; i < a.size(); i++) {
                        arr[0][i] = make_pair(a[i], i);
                }
                for (ll i = 1; i <= lg.back(); i++) {
                        for (ll j = 0; j + (1 << (i - 1)) < a.size(); j++) {
                                arr[i][j] = max(arr[i - 1][j], arr[i - 1][j + (1 << (i - 1))]);
                        }
                }
        }
        pair<ll, ll> get(ll l, ll r) {
                return max(arr[lg[r - l]][l], arr[lg[r - l]][r - (1 << lg[r - l])]);
        }
};

void solve() {
        ll n, q;
        cin >> n >> q;
        vector<ll> arr(n);
        for (ll i = 0; i < n; i++) {
                cin >> arr[i];
        }
        sparce_table st(arr);
        for (ll i = 0; i < q; i++) {
                ll l, r, t;
                cin >> t >> l >> r;
                l--;
                cout << st.get(max(0ll, l - t), r).first << '\n'; 
        }
}

int main() {
        if (IS_FILE) {
                freopen("", "r", stdin);
                freopen("", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll t = 1;
        if (IS_TEST_CASES) {
                cin >> t;
        }
        for (ll i = 0; i < t; i++) {
                solve();
        }
}

Compilation message

ho_t5.cpp: In constructor 'sparce_table::sparce_table(std::vector<long long int>)':
ho_t5.cpp:57:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                         if ((1 << (lg.back() + 1)) == lg.size() - 1) {
      |                             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:62:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 for (ll i = 0; i < a.size(); i++) {
      |                                ~~^~~~~~~~~~
ho_t5.cpp:66:59: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                         for (ll j = 0; j + (1 << (i - 1)) < a.size(); j++) {
      |                                        ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:94:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:95:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 125 ms 66160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 112 ms 65748 KB Output is correct
3 Correct 114 ms 64668 KB Output is correct
4 Correct 123 ms 67396 KB Output is correct
5 Correct 115 ms 65504 KB Output is correct
6 Correct 108 ms 66140 KB Output is correct
7 Correct 116 ms 66488 KB Output is correct
8 Correct 118 ms 65544 KB Output is correct
9 Correct 118 ms 64840 KB Output is correct
10 Correct 140 ms 64464 KB Output is correct
11 Correct 138 ms 67204 KB Output is correct
12 Correct 118 ms 66764 KB Output is correct
13 Correct 122 ms 66652 KB Output is correct
14 Correct 132 ms 65160 KB Output is correct
15 Correct 150 ms 67252 KB Output is correct
16 Correct 116 ms 66796 KB Output is correct

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -