oj.uz

답안 #1078866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078866 2024-08-28T07:28:03 Z The_Samurai 송신탑 (IOI22_towers) C++17
0 / 100
 700 ms 20536 KB 
#include "towers.h"
#include "bits/stdc++.h"
using namespace std;

struct segtree {
    vector<pair<int, int>> tree;
    int size;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size, make_pair(0, 0));
    }

    void upd(int i, pair<int, int> v) {
        i += size;
        tree[i] = max(tree[i], v);
        for (; i > 1; i >>= 1) tree[i >> 1] = max(tree[i], tree[i ^ 1]);
    }

    pair<int, int> get(int l, int r) {
        if (l > r) return make_pair(0, 0);
        pair<int, int> res = make_pair(0, 0);
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, tree[l++]);
            if (r & 1) res = max(res, tree[--r]);
        }
        return res;
    }
};

int n;
vector<int> a;
segtree sg1, sg2;
const int lg = 17;
vector<vector<int>> jump;
set<pair<int, int>, greater<>> st;

void init(int _n, std::vector<int> _a) {
    n = _n;
    a = _a;
    jump = vector(lg + 1, vector(n, -1));
    st.clear();
    vector<int> all, v;
    for (int i = 0; i < n; i++) {
        all.emplace_back(a[i]);
        all.emplace_back(a[i] + 1);
    }
    sort(all.begin(), all.end());
    for (int i = 0; i < all.size(); i++) {
        if (i > 0 and all[i] == all[i - 1]) continue;
        v.emplace_back(all[i]);
    }
    int z = all.size();
    sg1.init(z + 1); sg2.init(z + 1);

    for (int i = 0; i < n; i++) {
        int pos = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        int pos2 = lower_bound(v.begin(), v.end(), a[i] + 1) - v.begin();
        auto it = sg1.get(pos2, z);
        if (it.first > 0) jump[0][i] = it.second;
        it.second = i;
        it.first++;
        sg2.upd(pos2, it);
        sg1.upd(pos, sg2.get(0, pos));
    }
    for (int i = 1; i < n; i++) {
        if (jump[0][i] == -1) continue;
        for (int j = 1; j < lg; j++) {
            jump[j][i] = jump[j - 1][jump[j - 1][i]];
            if (jump[j][i] == -1) break;
        }
    }
    for (int l = 0, r = 0; r < n; r++) {
        if (r == n - 1 or a[r] > a[r + 1]) {
            st.emplace(l, r);
            l = r + 1;
        }
    }
}

int max_towers(int l, int r, int d) {
    auto it = st.upper_bound(make_pair(r, (int) 1e9));
    if (l > it->first) return 1;
    int i = it->first, ans = 1;
    for (int j = lg - 1; j >= 0; j--) {
        if (jump[j][i] < l) continue;
        ans += 1 << j;
        i = jump[j][i];
    }
    return ans;
}

Compilation message

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < all.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 346 ms 10728 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 700 ms 20536 KB 29th lines differ - on the 1st token, expected: '9839', found: '9838'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 233 ms 5260 KB 1st lines differ - on the 1st token, expected: '7197', found: '8004'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 346 ms 10728 KB 2nd lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -