Translation Notice
This article was machine-translated using DeepSeek-R1.

Original Version: Authored in Chinese by myself

Accuracy Advisory: Potential discrepancies may exist between translations

Precedence: The Chinese text shall prevail in case of ambiguity

Feedback: Technical suggestions regarding translation quality are welcomed

D - Sequence Query

Problem Summary

We have an empty sequence $A$. Process $Q$ commands in order, each of three types:

1 x: Add $x$ to $A$ (without deduplication)
2 x k: Find the $k$-th largest value among elements $\le x$ in $A$.
3 x k: Find the $k$-th smallest value among elements $\ge x$ in $A$.

$1\le Q\le 2\times 10^5$
$1\le x\le 10^{18}$
==$1\le k\le 5$==

Analysis

Given $1\le k\le 5$, we can use multiset.
multiset supports binary search. For details, see here.
For each query:

1 x: Directly insert into multiset
2 x k: Use upper_bound, then move iterator backward $k$ steps
3 x k: Use lower_bound, then move iterator forward $k$ steps

Due to small $k$, moving iterators is negligible.
Time complexity: Optimal $\mathcal O(Q)$, average $\mathcal O(Q\log Q)$, worst $\mathcal O(Q\log Q)$.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


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

int main()
{
    multiset<long long> s;
    int q;
    scanf("%d", &q);
    while(q--)
    {
        int op;
        long long x;
        scanf("%d%lld", &op, &x);
        if(op == 1) s.insert(x);
        else
        {
            int k;
            scanf("%d", &k);
            if(op == 2)
            {
                bool bad = false;
                auto it = s.upper_bound(x);
                for(; k--; --it)
                    if(it == s.begin())
                    {
                        bad = true;
                        break;
                    }
                if(bad) puts("-1");
                else printf("%lld\n", *it);
            }
            else
            {
                auto it = s.lower_bound(x);
                for(; --k; ++it)
                    if(it == s.end())
                        break;
                if(it == s.end()) puts("-1");
                else printf("%lld\n", *it);
            }
        }
    }
    return 0;
}

E - Putting Candies

Problem Summary

Given sequence $A=(A_0,A_1,\dots,A_{N-1})$.
Start with an empty plate. Takahashi adds $A_{(X\bmod N)}$ candies each time (where $X$ is current candy count).
Find total candies after $K$ operations.

$2\le N\le 2\times 10^5$
$1\le K\le 10^{12}$
$1\le A_i\le 10^6$

Analysis

By pigeonhole principle, $A_{(X\bmod N)}$ must repeat within $N$ operations.
This becomes a periodic problem. We record time mappings to reconstruct cycles.
Time complexity: $\mathcal O(n)$, space complexity: $\mathcal O(n)$.

Code

Code reference: AtCoder Editorial

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


#include <cstdio>
#define maxn 200005
using namespace std;

using LL = long long;
LL A[maxn], S[maxn];
int pre[maxn];

int main()
{
    int n;
    LL k;
    scanf("%d%lld", &n, &k);
    for(int i=0; i<n; i++)
        scanf("%lld", A + i);
    for(int i=1; i<n; i++)
        pre[i] = -1;
    int time, s;
    for(int i=0; i<n; i++)
    {
        S[i + 1] = S[i] + A[S[i] % n];
        if(pre[S[i + 1] % n] != -1)
        {
            s = pre[S[i + 1] % n];
            time = i + 1;
            break;
        }
        pre[S[i + 1] % n] = i + 1;
    }
    if(k <= s) printf("%lld\n", S[k]);
    else
    {
        int p = time - s;
        LL X = S[time] - S[s], t = k - s - 1;
        printf("%lld\n", S[s + t % p + 1] + t / p * X);
    }
    return 0;
}

F - Skate

Problem Summary

Given $H\times W$ grid with $N$ obstacles at $(X_i,Y_i)$.
Start at $(s_x,s_y)$, slide in up/down/left/right until hitting an obstacle, stopping at the preceding cell. Find minimum steps to reach $(g_x,g_y)$. Output -1 if impossible.

$1\le H,W\le 10^9$
==$1\le N\le 10^5$==
$1\le s_x,g_x,X_i\le H$
$1\le s_y,g_y,Y_i\le W$
$(s_x,s_y)\ne(g_x,g_y)\ne(X_i,Y_i)$
All $(X_i,Y_i)$ are distinct.

Analysis

Despite large grid dimensions, $N$ is manageable. Use BFS with map/set to track rows/columns. For each coordinate, binary search nearby obstacles.

Code

Notes:

Row/column coordinates must be sorted (can use set)
Handle binary search boundaries carefully

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


#include <cstdio>
#include <queue>
#include <set>
#include <unordered_map>
using namespace std;

using LL = long long;
unordered_map<int, set<int>> row, col;
unordered_map<LL, int> dis;

inline LL pack(LL x, int y) { return x << 31LL | y; }
inline void unpack(const LL& b, int& x, int& y) { x = b >> 31LL, y = b & 0x7fffffff; }

int main()
{
    int h, w, n, sx, sy, gx, gy;
    scanf("%d%d%d%d%d%d%d", &h, &w, &n, &sx, &sy, &gx, &gy);
    for(int i=0; i<n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        row[x].insert(y);
        col[y].insert(x);
    }
    LL target = pack(gx, gy);
    queue<pair<LL, int>> q;
    q.emplace(pack(sx, sy), 0);
    while(!q.empty())
    {
        auto [p, d] = q.front(); q.pop();
        if(!dis.emplace(p, d).second) continue;
        if(p == target) { printf("%d\n", d); return 0; }
        int x, y;
        unpack(p, x, y), ++d;
        if(row.count(x))
        {
            auto& s = row[x];
            auto it = s.lower_bound(y);
            if(it != s.end()) q.emplace(pack(x, *it - 1), d);
            if(it != s.begin()) q.emplace(pack(x, *--it + 1), d);
        }
        if(col.count(y))
        {
            auto& s = col[y];
            auto it = s.lower_bound(x);
            if(it != s.end()) q.emplace(pack(*it - 1, y), d);
            if(it != s.begin()) q.emplace(pack(*--it + 1, y), d);
        }
    }
    puts("-1");
    return 0;
}