| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1308625 | orzorzorz | 팀들 (IOI15_teams) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 500005;
struct Node {
int count;
Node *left, *right;
Node(int count, Node *left, Node *right) : count(count), left(left), right(right) {}
};
Node* null;
Node* roots[MAXN]; // Persistent Tree Roots
// Build initial empty tree
Node* build(int l, int r) {
if (l == r) return new Node(0, null, null);
int mid = l + (r - l) / 2;
return new Node(0, build(l, mid), build(mid + 1, r));
}
// Update: Add a student with B_val at position p
Node* update(Node* node, int l, int r, int p) {
if (l == r) return new Node(node->count + 1, null, null);
int mid = l + (r - l) / 2;
if (p <= mid) return new Node(node->count + 1, update(node->left, l, mid, p), node->right);
else return new Node(node->count + 1, node->left, update(node->right, mid + 1, r, p));
}
// Query: Count students in range [ql, qr] in a specific tree version
int query(Node* node, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return node->count;
int mid = l + (r - l) / 2;
return query(node->left, l, mid, ql, qr) + query(node->right, mid + 1, r, ql, qr);
}
int N;
vector<int> adj[MAXN]; // Store B_i for each A_i
// Helper to get count of students with A <= x AND B in [y1, y2]
int count_students(int x, int y1, int y2) {
if (y1 > y2) return 0;
return query(roots[x], 1, N, y1, y2);
}
// Initial Setup
void init(int n, int A[], int B[]) {
N = n;
null = new Node(0, nullptr, nullptr);
null->left = null->right = null;
roots[0] = build(1, N);
// Group students by A value
for (int i = 0; i < N; i++) {
adj[A[i]].push_back(B[i]);
}
// Build Persistent Tree
for (int i = 1; i <= N; i++) {
roots[i] = roots[i-1];
for (int b : adj[i]) {
roots[i] = update(roots[i], 1, N, b);
}
}
}
// The Stack Solver
int can(int M, int K[]) {
sort(K, K + M);
// Stack stores pairs: {split_point_B, number_removed}
// It represents the "corners" of the forbidden region
struct Element {
int k_val; // The group size K that created this constraint
int removed; // How many valid students were used up to this point
};
vector<Element> st;
st.push_back({0, 0});
for (int i = 0; i < M; i++) {
int k = K[i];
// Remove stack elements that are 'dominated' by the current k.
// We are looking for the 'tightest' previous constraint.
while (st.size() > 1) {
Element top = st.back();
Element prev = st[st.size() - 2];
// Calculate how many students are between the previous split and current top
// range: A <= top.k_val, B in [prev.k_val + 1, k]
int diff = count_students(top.k_val, prev.k_val + 1, k);
// If the current k requires more students than available in this slice,
// or effectively "covers" the previous constraint, we pop.
// (Note: The specific condition depends on the specific Hall's logic,
// but simply: if the jump from prev to top is small, we merge).
// Actually, for the IOI solution, we use the property:
// We pop if the 'removed' count calculation implies the intersection is higher.
int available_in_segment = count_students(top.k_val, prev.k_val + 1, top.k_val);
if (top.removed + diff >= prev.removed + available_in_segment) {
// Optimization: This stack check is tricky.
// Standard implementation usually just computes the new 'removed'
// and checks feasibility.
break; // Simplified for explanation, see full logic below
}
st.pop_back();
}
// Correct Minimal Logic for IOI (Commonly used template):
while (st.size() > 1) {
Element back = st.back();
int low = st[st.size()-2].k_val + 1;
int high = back.k_val;
// Count students valid for the 'back' group but strictly BELOW current k in B-value
int count = count_students(back.k_val, low, high);
if (back.removed + count_students(back.k_val, high+1, k) >= st[st.size()-2].removed + count) {
// The current K is more restrictive, pop the previous
st.pop_back();
} else {
break;
}
}
Element last = st.back();
// Number of students we effectively remove:
// previous_removed + students in range [last.k_val+1, k] with A <= k
int used = last.removed + count_students(last.k_val, last.k_val + 1, k) + k;
// Total students available for current k: A <= k, B >= k
int total_avail = count_students(k, 1, N) - count_students(k, 1, k - 1); // effectively B >= k
// But more accurately using the persistent tree directly:
// The check:
// We need 'k' new students.
// total needed = last.removed + count(between last.k and k) + k
// max available = count(A <= k, B >= last.k + 1)
// Let's use the simplest specific check:
int needed = last.removed + k;
int available = count_students(k, last.k_val + 1, k); // Contribution from this slice
// This is getting mathematically messy in comments.
// The clean check is:
int quantity = last.removed + k; // Total demand up to this point
int supply_limit = count_students(k, last.k_val + 1, k); // supply in the strip
// The standard IOI logic simply updates the "removed" count for the new stack entry:
int new_removed = last.removed + count_students(last.k_val, last.k_val + 1, k) + k;
// Feasibility check:
// available total in A <= k and B >= k must be >= new_removed
if (new_removed > count_students(k, 1, N)) return 0; // Rough upper bound check
// Exact Hall Check:
// count(A<=k, B >= last.k_val + 1) must be >= new_removed - last.removed
if (count_students(k, last.k_val + 1, N) < new_removed - last.removed) return 0;
st.push_back({k, new_removed});
}
return 1;
}
int main() {
// Driver code would go here
return 0;
}