Submission #1271780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271780		cbnk32_tuandung	Pilot (NOI19_pilot)	C++17	40 / 100	19 ms	3908 KiB

pilot

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

/*
run
 g++ PILOT.cpp -std=c++1y -o run.exe && ./run.exe
*/

// CONSTANTs

constexpr int MAX_N = 1000000 + 6;
constexpr int MAX_A = 1000000 + 6;

// GIVEN

int N, Q;
int A[MAX_N];
pair<int, int> q[MAX_N];

// VARIABLEs

long long ANS[MAX_N];

// FUNCTIONs

// SUBTASKs

bool checkSub6 = true;
bool checkSub7 = true;

namespace sub1234 {
    bool checkInput() {
        return (max(N, Q) <= 1000);
    }

    int X;

    int solve() {
        while (Q--) {
            cin >> X;
            long long res = 0;
            int streak = 0;
            for (int i = 1; i <= N; ++i) {
                if (A[i] > X) {
                    res += 1ll * streak * (streak + 1) / 2;
                    streak = 0;
                } else ++streak;
            }
            res += 1ll * streak * (streak + 1) / 2;
            cout << res << "\n";
        }
        return 0;
    }
}

namespace sub5 {
    bool checkInput() {
        return ((Q == 1) && (q[1].first == 1000000));
    }
    int solve() {
        long long res = N;
        res = res * (N + 1);
        res >>= 1;
        cout << res << "\n";
        return 0;
    }
}

namespace sub8 {
    bool checkInput() {
        return (Q == 1);
    }

    int X;

    int solve() {
        // cin >> X;
        X = q[1].first;
        long long res = 0;
        int streak = 0;
        for (int i = 1; i <= N; ++i) {
            if (A[i] > X) {
                res += 1ll * streak * (streak + 1) / 2;
                streak = 0;
            } else ++streak;
        }
        res += 1ll * streak * (streak + 1) / 2;
        cout << res << "\n";
        return 0;
    }
}

namespace sub67 {
    bool checkInput() {
        return (checkSub6 || checkSub7);
    }

    int solve() {
        for (int i = 1; i <= Q; ++i) {
            int tmp = upper_bound(A + 1, A + 1 + N, q[i].first) - A;
            if (tmp > N) ANS[i] = 1ll * (1ll * N * (N + 1)) / 2;
            else ANS[i] = 1ll * tmp * (tmp - 1) / 2;
            cout << ANS[i] << "\n";
        }
        return 0;
    }
}

// namespace sub9 {
//     bool checkInput() {
//         return true;
//     }
//     int solve() {
//         int stat = 1;
//         for (int _ = 1; _ <= Q; ++_) {
//             long long res = 0;
//             int i = stat;
//             while (A[i] > q[_].first) {
//                 ++i;
//                 ++stat;
//             }
//             while (i <= N) {
//                 int j = upper_bound(A + i, A + 1 + N, q[_].first) - A;
//                 if (j > N) {
//                     res += 1ll * (N - i + 1) * (N - i + 2) / 2;
//                     break;
//                 }
//                 res += 1ll * (j - i) * (j - i + 1) / 2;
//                 i = j + 1;
//             }
//         }
//     }
// }

namespace AC {
    void solve() {
        for (int i = 1; i <= N; ++i) {

        }
    }
}

// MAIN

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

    // freopen("PILOT.INP", "r", stdin);
    // freopen("PILOT.OUT", "w", stdout);
    
    cin >> N >> Q;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        q[i] = {A[i], i};
        checkSub6 = checkSub6 && (A[i] == i);
        checkSub7 = checkSub7 && (A[i] > A[i - 1]);
    }

    if (sub1234::checkInput()) return sub1234::solve();

    for (int i = 1; i <= Q; ++i) {
        cin >> q[i + N].first;
        q[i + N].second = i + N;
    }

    if (sub5::checkInput())  return  sub5::solve();
    if (sub67::checkInput()) return sub67::solve();
    if (sub8::checkInput())  return  sub8::solve();
    AC::solve();
    // sort(q + 1, q + 1 + Q);
    // if (sub9::checkInput())  return  sub9::solve();
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 0 / 5
• Subtask 6: 0 / 9
• Subtask 7: 0 / 14
• Subtask 8: 0 / 10
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11