Contest Preparation Algorithm

This solution handles two special cases before applying the general formulla:

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    if (n == 0) {
        cout << 0 << endl;
    } else if (n <= m) {
        cout << 2 << endl;
    } else {
        cout << (2 * n + m - 1) / m << endl;
    }
    return 0;
}

Difference Calculation with Binary Search

This approach uses binary search combined with sliding window and deque structures to efficiently find the maximum value where the number of valid subarrays meets the threshold:

#include <deque>
#include <vector>
#include <iostream>
using namespace std;

typedef long long ll;

ll countValidRanges(const vector<ll>& arr, ll threshold) {
    ll count = 0;
    deque<ll> minDeque, maxDeque;
    ll left = 0;
    
    for (ll right = 0; right < arr.size(); right++) {
        while (!minDeque.empty() && arr[minDeque.back()] >= arr[right])
            minDeque.pop_back();
        minDeque.push_back(right);
        
        while (!maxDeque.empty() && arr[maxDeque.back()] <= arr[right])
            maxDeque.pop_back();
        maxDeque.push_back(right);
        
        while (left <= right && (arr[maxDeque.front()] - arr[minDeque.front()]) * (right - left + 1) >= threshold) {
            if (maxDeque.front() == left) maxDeque.pop_front();
            if (minDeque.front() == left) minDeque.pop_front();
            left++;
        }
        count += left;
    }
    return count;
}

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> values(n);
    for (ll i = 0; i < n; i++) cin >> values[i];
    
    ll low = 1, high = 1e18, result = 0;
    while (low <= high) {
        ll mid = (low + high) / 2;
        if (countValidRanges(values, mid) >= k) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << result << endl;
    return 0;
}

Triangle Counting on Grid

This solution counts triangles formed by grid points using dynamic programming:

#include <iostream>
#include <vector>
using namespace std;

const int GRID_SIZE = 510;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> grid(GRID_SIZE, vector<int>(GRID_SIZE, 0));
    
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        grid[x][y] = 1;
    }
    
    for (int i = 1; i < GRID_SIZE; i++) {
        for (int j = 1; j < GRID_SIZE; j++) {
            if (grid[i][j]) {
                grid[i][j] += grid[i-1][j-1];
            }
        }
    }
    
    long long total = 0;
    for (int i = 0; i < GRID_SIZE; i++) {
        for (int j = 0; j < GRID_SIZE; j++) {
            total += grid[i][j];
        }
    }
    
    cout << total * 2 << endl;
    return 0;
}

XOR Transformation Problem

This solution determines whether an array can be transformed to all zeros using XOR operations based on array length parity:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> arr(n);
    long long xorSum = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        xorSum ^= arr[i];
    }
    
    if (xorSum == 0 || n % 2 == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}