제출 #1309559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309559		ayuxhkumxr22	Exercise Deadlines (CCO20_day1problem2)	C++20	25 / 25	55 ms	12936 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// Fenwick Tree (BIT) for counting inversions efficiently
// Handles point updates and prefix sum queries
struct FenwickTree {
    int size;
    vector<int> tree;

    FenwickTree(int n) : size(n), tree(n + 1, 0) {}

    void add(int index, int value) {
        while (index <= size) {
            tree[index] += value;
            index += index & (-index);
        }
    }

    int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & (-index);
        }
        return sum;
    }
};

void solve() {
    int N;
    if (!(cin >> N)) return;

    // We need to group tasks by their deadline.
    // tasks_by_deadline[t] stores all tasks with deadline exactly t.
    vector<vector<int>> tasks_by_deadline(N + 1);
    
    for (int i = 1; i <= N; i++) {
        int d;
        cin >> d;
        tasks_by_deadline[d].push_back(i);
    }

    // Max-heap to store available tasks (prioritizing largest original index)
    priority_queue<int> pq;
    
    // This will store our final constructed schedule
    // result_schedule[i] = the task done at time i+1 (0-indexed logic)
    vector<int> result_schedule(N);

    // Iterate backwards from time t = N down to 1
    for (int t = N; t >= 1; t--) {
        // Add all tasks that have a deadline exactly at t to the pool
        for (int task_id : tasks_by_deadline[t]) {
            pq.push(task_id);
        }

        if (pq.empty()) {
            // No task available that can be done at time t or later
            cout << "-1" << endl;
            return;
        }

        // Greedy choice: Pick the task with the LARGEST index
        result_schedule[t - 1] = pq.top();
        pq.pop();
    }

    // Step 2: Count inversions in result_schedule using Fenwick Tree
    long long inversions = 0;
    FenwickTree bit(N);

    // Standard inversion counting:
    // Iterate through the array, for each element x:
    // Inversions += (elements seen so far that are greater than x)
    // This equals: (total elements seen) - (elements seen <= x)
    for (int i = 0; i < N; i++) {
        int current_val = result_schedule[i];
        
        // Count how many numbers already processed are larger than current_val
        int count_smaller = bit.query(current_val);
        int count_total_seen = i; // we have processed i elements so far
        
        inversions += (count_total_seen - count_smaller);
        
        // Add current value to BIT
        bit.add(current_val, 1);
    }

    cout << inversions << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 8 / 8