ABC391

D - Gravity

#include <bits/stdc++.h>
using namespace std;
const int MAXW = 200000;
const int MAXN = 200000;
int n, w;
// q[i] 存第 i 列的方块的行数的相反数（小根堆）以及编号
priority_queue<pair<int, int>> q[MAXW + 5];
// ans[i] 记录第 i 个方格的消失时间
int ans[MAXN + 5];
int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; i++)
    {
        int xi, yi; // 列、行
        cin >> xi >> yi;
        q[xi].push(make_pair(-yi, i));
        ans[i] = 0;
    }
    for (bool flag = true; flag;)
    {
        // 找到当前最后一行啥时候能消除
        int now = -1;
        for (int i = 1; i <= w; i++)
        {
            if (q[i].empty())
            {
                now = -1;
                break;
            }
            now = max(now, -q[i].top().first);
        }
        if (now == -1)
            break;
        for (int i = 1; i <= w; i++)
        {
            pair<int, int> block = q[i].top();
            q[i].pop();
            ans[block.second] = now;
        }
    }
    int Q;
    cin >> Q;
    while (Q--)
    {
        int ti, ai;
        cin >> ti >> ai;
        if (ans[ai] != 0 && ans[ai] <= ti)
            cout << "No\n";
        else
            cout << "Yes\n";
    }

    return 0;
}

E - Hierarchical Majority Vote

#include <bits/stdc++.h>
using namespace std;
int n;
string A;
// <数字，几次能反转>
queue<pair<int, int>> q, qq;
// 三个数的计算，返回<变成了几，操作几次可以反转>
pair<int, int> f(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
    pair<int, int> res;
    int now = a.first + b.first + c.first;
    int cnt = a.second + b.second + c.second;
    res.first = (now >= 2);
    if (now == 3 || now == 0)
    {
        // 反转两个操作次数最少的（找到一个操作次数最多的）
        int maxSe = a.second;
        maxSe = max(maxSe, b.second);
        maxSe = max(maxSe, c.second);
        res.second = cnt - maxSe;
    }
    else
    {
        // 找一个最小的 x（0或1） 反转
        int x = (now == 2);
        int minSe = cnt;
        if (a.first == x)
            minSe = min(minSe, a.second);
        if (b.first == x)
            minSe = min(minSe, b.second);
        if (c.first == x)
            minSe = min(minSe, c.second);
        res.second = minSe;
    }
    return res;
}
int main()
{
    cin >> n;
    cin >> A;
    for (int i = 0; i < A.size(); i++)
        q.push(make_pair(A[i] - '0', 1));
    for (int i = 1; i <= n; i++)
    {
        while (!q.empty())
        {
            pair<int, int> a, b, c;
            a = q.front();
            q.pop();
            b = q.front();
            q.pop();
            c = q.front();
            q.pop();
            qq.push(f(a, b, c));
        }
        swap(q, qq);
    }
    cout << q.front().second << "\n";
    return 0;
}