Problem A - AtCoder Line Straightforward check: determine whether point z lies between x and y on the number line. Simply swap if necessary to ansure x ≤ y, then verify the condition. Click to view code

#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int n, p, q, r;
    scanf("%d%d%d%d", &n, &p, &q, &r);
    if (p > q) swap(p, q);
    printf("%s\n", p <= r && r <= q ? "Yes" : "No");
    return 0;
}

Problem B - Typing Use two pointers to scan through both strings. For each character in string t, check if it matches the current character in string s. When matched, output the position and advance the pointer in s. Click to view code

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 200005;
int len1, len2;
char str1[MAXN], str2[MAXN];

int main()
{
    scanf("%s%s", str1 + 1, str2 + 1);
    len1 = strlen(str1 + 1);
    len2 = strlen(str2 + 1);
    for (int i = 1, j = 1; j <= len2; j++)
        if (str1[i] == str2[j])
        {
            printf("%d ", j);
            i++;
        }
    return 0;
}

Problem C - Standing On The Shoulders The total shoulder height remains constant regardless of arrangement. The final height equals the sum of all shoulder heights plus the head height of the person on top. The head height is computed as height - shoulder_height. To maximize the total, place the person with maximum head height at the top. Formula: sum(a_i) + max(b_i - a_i) Click to view code

#include <cstdio>
using namespace std;

const int MAXN = 200005;
int n;
int shoulder[MAXN], height[MAXN];

int main()
{
    scanf("%d", &n);
    long long base = 0;
    int bestHead = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &shoulder[i], &height[i]);
        base += shoulder[i];
        bestHead = max(bestHead, height[i] - shoulder[i]);
    }
    printf("%lld\n", base + bestHead);
    return 0;
}

Problem D - Permutation Subsequence First, record the position of each value: position[value] = index. For any consecutive subsequence of length k in the original array, the positions form a set of k consecutive values. The minimum window width across all such subsequences gives the answer. We need to compute: min over all windows (max position - min position) Maintain two monotonic deques - one for maximum positions and one for minimum positions - to efficiently track the window boundaries.

#include <cstdio>
using namespace std;

const int MAXN = 200005;
int n, k;
int arr[MAXN], pos[MAXN];
int maxDeque[MAXN], minDeque[MAXN];
int frontMax = 1, backMax = 0;
int frontMin = 1, backMin = 0;

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
        pos[arr[i]] = i;
    }
    int answer = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
    {
        // Maintain max deque
        while (frontMax <= backMax && i - maxDeque[frontMax] + 1 > k) frontMax++;
        while (frontMax <= backMax && pos[i] > pos[maxDeque[backMax]]) backMax--;
        maxDeque[++backMax] = i;
        
        // Maintain min deque
        while (frontMin <= backMin && i - minDeque[frontMin] + 1 > k) frontMin++;
        while (frontMin <= backMin && pos[i] < pos[minDeque[backMin]]) backMin--;
        minDeque[++backMin] = i;
        
        if (i - k + 1 >= 1)
            answer = min(answer, pos[maxDeque[frontMax]] - pos[minDeque[frontMin]]);
    }
    printf("%d\n", answer);
    return 0;
}

Problem E - Clique Connect Each operation creates a complete graph (clique) among a set of vertices with uniform edge weight. We need to find the minimum total cost to connect all vertices. Applying Kruskal's algorithm conceptually: process all clique in order of increasing weight. For each clique, attempt to connect all unconnected vertices within it. Since all edges in a clique have the same weight, we only need to add edges until all vertex in that clique become connected. Use a union-find (disjoint set union) structure to maintain connectivity. Sort all operations by weight, then iterate through them, merging components and accumulating costs whenever a merge actually connects two previously disconnected sets.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 200005;
const int MAXM = 400005;
int numVertices, numOps;
pair<int, int> ops[MAXM];
vector<int> vertices[MAXM];

int parent[MAXN], size[MAXN];

void initDSU()
{
    for (int i = 1; i <= numVertices; i++)
    {
        parent[i] = i;
        size[i] = 1;
    }
}

int findSet(int x)
{
    return parent[x] == x ? x : parent[x] = findSet(parent[x]);
}

void unionSets(int x, int y)
{
    x = findSet(x);
    y = findSet(y);
    if (size[x] < size[y]) swap(x, y);
    size[x] += size[y];
    parent[y] = x;
}

int main()
{
    scanf("%d%d", &numVertices, &numOps);
    for (int i = 1; i <= numOps; i++)
    {
        int cnt;
        scanf("%d", &cnt);
        scanf("%d", &ops[i].first);
        ops[i].second = i;
        vertices[i].resize(cnt);
        for (int j = 0; j < cnt; j++)
            scanf("%d", &vertices[i][j]);
    }
    sort(ops + 1, ops + numOps + 1);
    long long totalCost = 0;
    initDSU();
    for (int i = 1; i <= numOps; i++)
    {
        vector<int> &current = vertices[ops[i].second];
        for (size_t j = 1; j < current.size(); j++)
        {
            if (findSet(current[0]) != findSet(current[j]))
            {
                unionSets(current[0], current[j]);
                totalCost += ops[i].first;
            }
        }
    }
    bool connected = true;
    int root = findSet(1);
    for (int i = 1; i <= numVertices; i++)
    {
        if (findSet(i) != root)
        {
            connected = false;
            break;
        }
    }
    if (connected) printf("%lld\n", totalCost);
    else puts("-1");
    return 0;
}