Submission #1107139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107139		serifefedartar	Triple Jump (JOI19_jumps)	C++17	0 / 100	285 ms	14596 KiB

jumps

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

#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 998244353;
const ll MAXN = 5e5 + 100;

const ll SQRT = 700;

#define int long long
vector<array<int,3>> queries;
vector<int> A;
int ans[MAXN];
multiset<pair<int,int>> st;
void add(int x) {
    st.insert({A[x], x});
}

void omit(int x) {
    st.erase(st.find({A[x], x}));
}

signed main() {
    fast;
    int N, Q;
    cin >> N;

    vector<vector<int>> msk;
    for (int mask = 0; mask < 1e6; mask++) {
        vector<int> Q;
        for (int bit = 0; bit < 25; bit++) {
            if ((1<<bit) & mask)
                Q.push_back(bit);
        }
        if (Q.size() == 3)
            msk.push_back(Q);
    }

    A = vector<int>(N+1);
    for (int i = 1; i <= N; i++)
        cin >> A[i];

    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        int l, r;
        cin >> l >> r;
        queries.push_back({l, r, i});
    }
    sort(queries.begin(), queries.end(), [&](array<int,3> A, array<int,3> B) {
        return make_pair(A[0] / SQRT, A[1]) < make_pair(B[0] / SQRT, B[1]);
    });

    int l = 1, r = 1;
    st.insert({A[1], 1});
    for (auto u : queries) {
        array<int,3> Q = u;

        while (Q[1] > r) {
            r++;
            add(r);
        }

        while (Q[0] < l) {
            l--;
            add(l);
        }

        while (Q[1] < r) {
            omit(r);
            r--;
        }

        while (Q[0] > l) {
            omit(l);
            l++;
        }

        vector<pair<int,int>> v;
        int x = 0;
        while (st.size() && x < 20) {
            x++;
            v.push_back(*prev(st.end()));
            st.erase(prev(st.end()));
        }
        sort(v.begin(), v.end(), [&](pair<int,int> A, pair<int,int> B) {
            return A.s < B.s;
        });

        int res = 0; 
        for (auto u : msk) {
            if (u[1] - u[0] > u[2] - u[1] || u[2] >= v.size())
                continue;

            int now = 0;
            for (auto q : u)
                now += v[q].f;
            res = max(res, now);
        }

        for (auto u : v)
            st.insert(u);
        ans[Q[2]] = res;
    }

    for (int i = 1; i <= Q; i++)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:95:51: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             if (u[1] - u[0] > u[2] - u[1] || u[2] >= v.size())

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54