Submission #1181816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181816		mehmetkagan	Solar Storm (NOI20_solarstorm)	C++17	36 / 100	395 ms	177720 KiB

SolarStorm

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

typedef long long ll;

struct Event {
    int pos;
    int type; // 0 add, 1 remove
    int x;
    Event(int p, int t, int xx) : pos(p), type(t), x(xx) {}
    bool operator<(const Event& other) const {
        if (pos != other.pos) return pos < other.pos;
        return type < other.type; // process remove first to avoid issues
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, S;
    ll K;
    cin >> N >> S >> K;

    vector<ll> d(N-1);
    for (int i=0; i<N-1; ++i) cin >> d[i];

    vector<int> v(N);
    for (int i=0; i<N; ++i) cin >> v[i];

    vector<ll> pos(N);
    pos[0] = 0;
    for (int i=1; i<N; ++i) pos[i] = pos[i-1] + d[i-1];

    vector<ll> left(N, 0), right(N, 0);
    for (int x=0; x<N; ++x) {
        ll px = pos[x];
        // left_x: first j where pos[j] >= px - K
        int l = 0, r = x;
        int best_l = x;
        while (l <= r) {
            int mid = (l + r)/2;
            if (pos[mid] >= px - K) {
                best_l = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        left[x] = best_l;

        // right_x: last j where pos[j] <= px + K
        l = x;
        r = N-1;
        int best_r = x;
        while (l <= r) {
            int mid = (l + r)/2;
            if (pos[mid] <= px + K) {
                best_r = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        right[x] = best_r;
    }

    vector<Event> events;
    for (int x=0; x<N; ++x) {
        events.emplace_back(left[x], 0, x);
        events.emplace_back(right[x]+1, 1, x);
    }
    sort(events.begin(), events.end());

    vector<int> farthest_reach(N, 0);
    vector<int> best_x(N, -1);
    auto cmp = [&](int a, int b) {
        if (right[a] != right[b]) return right[a] > right[b];
        return a < b;
    };
    set<int, decltype(cmp)> active_x(cmp);
    int event_ptr = 0;

    vector<ll> sum_v(N+1, 0);
    for (int i=0; i<N; ++i) sum_v[i+1] = sum_v[i] + v[i];

    for (int i=0; i<N; ++i) {
        while (event_ptr < events.size() && events[event_ptr].pos <= i) {
            Event e = events[event_ptr];
            if (e.type == 0) {
                active_x.insert(e.x);
            } else {
                active_x.erase(e.x);
            }
            event_ptr++;
        }
        if (!active_x.empty()) {
            int x = *active_x.begin();
            farthest_reach[i] = right[x];
            best_x[i] = x;
        } else {
            farthest_reach[i] = i-1; // cannot cover
            best_x[i] = -1;
        }
    }

    int LOG = 20;
    vector<vector<int>> jump(LOG, vector<int>(N, -1));
    for (int i=0; i<N; ++i) {
        if (best_x[i] == -1) {
            jump[0][i] = -1;
        } else {
            jump[0][i] = farthest_reach[i];
        }
    }
    for (int k=1; k<LOG; ++k) {
        for (int i=0; i<N; ++i) {
            if (jump[k-1][i] == -1) {
                jump[k][i] = -1;
            } else {
                int next_pos = jump[k-1][i] + 1;
                if (next_pos >= N) {
                    jump[k][i] = jump[k-1][i];
                } else if (jump[k-1][next_pos] == -1) {
                    jump[k][i] = -1;
                } else {
                    jump[k][i] = jump[k-1][next_pos];
                }
            }
        }
    }

    ll max_sum = -1;
    int best_L = 0, best_R = 0;

    for (int L=0; L<N; ++L) {
        int current = L;
        int rem = S;
        for (int k=LOG-1; k>=0; --k) {
            if (rem >= (1 << k) && current < N && jump[k][current] != -1) {
                current = jump[k][current] + 1;
                rem -= (1 << k);
            }
        }
        int R = current - 1;
        if (R < L) continue;
        R = min(R, N-1);
        ll current_sum = sum_v[R+1] - sum_v[L];
        if (current_sum > max_sum || (current_sum == max_sum && (best_R - best_L < R - L))) {
            max_sum = current_sum;
            best_L = L;
            best_R = R;
        }
    }

    vector<int> shields;
    int current = best_L;
    while (current <= best_R && shields.size() < S) {
        if (best_x[current] == -1) break;
        int x = best_x[current];
        shields.push_back(x + 1); // convert to 1-based
        current = right[x] + 1;
    }

    cout << shields.size() << endl;
    for (int x : shields) cout << x << " ";
    cout << endl;

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 8 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30