Submission #1170870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170870		Craftless	Marathon Race 2 (JOI24_ho_t3)	C++20	0 / 100	2 ms	324 KiB

Main

#include <bits/stdc++.h>

#define int long long int
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define INF 1e18

using namespace std;

// simulate both right to left to middle and left to right to middle

int N, L, Q, X[500010], B[500010], rmb = -INF, lmb = INF;

pi traverse(int s, int e, int b) {
    int k = 0;
    if (e > s) {
        for (int i = s; i < e; i++) {
            k += b + 1;
            if (B[i]) {
                k += B[i];
                b += B[i];
            }
        }
    }
    else {
        for (int i = s; i > e; i--) {
            k += b + 1;
            if (B[i]) {
                k += B[i];
                b += B[i];
            }
        }
    }
    return { k, b };
}

int32_t main() {

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        cin >> X[i];
        B[X[i]]++;
        rmb = max(rmb, X[i]);
        lmb = min(lmb, X[i]);
    }
    cin >> Q;
    while (Q--) {
        int s, e, t; cin >> s >> e >> t;
        // right
        int k = abs(rmb - s) - 1;
        int b = 0;
        pi t1 = traverse(rmb, lmb, b);
        b = t1.S;
        k += t1.F;
        pi t2 = traverse(lmb, e, b);
        b = t2.S;
        k += t2.F + b + 1;
        if (k <= t) {
            cout << "Yes\n";
            continue;
        }
        //left 
        k = abs(s - lmb) - 1;
        b = 0;
        t1 = traverse(lmb, rmb, b);
        b = t1.S;
        k += t1.F;
        t2 = traverse(rmb, e, b);
        b = t2.S;
        k += t2.F + b + 1;
        if (k <= t) {
            cout << "Yes\n";
            continue;
        }
        cout << "No\n";

        // for (int i = rmb; i >= lmb; i--) {
        //     if (B[i]) {
        //         k += B[i];
        //         b += B[i];
        //     }
        //     k += b + 1;
        // }
        // for (int i = lmb; i < N; i++) {
            
        // }
    }

    return 0;    
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 28
• Subtask 5: 0 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19