至道品牌设计公司_音乐网页设计素材_seo关键词优化软件手机_免费推广app平台有哪些

题目链接

Codeforces Round 950 (Div. 3) F1题 Field Division (easy version)

思路

我们按$r$从小到大，$c$从大到小进行排序。

预处理一个$nxt$数组，表示$c$的后缀最小值。这样，我们就可以利用$nxt$数组直接计算最开始时Alice所拥有的地块的最大面积。

遍历排序后的$r$和$c$，我们考虑使用单调栈。对于栈中的元素，我们保证从栈底到栈顶的元素的$c$的值是不断严格递增的。最后，对于栈中的元素，即为将该喷泉给予Alice之后Alice的最大地块面积会增大的喷泉。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, m, k;
int r[N], c[N];
struct node
{int r, c, id;
} p[N];
bool cmp1(node x, node y)
{if (x.r != y.r)return x.r < y.r;return x.c > y.c;
}
void solve()
{cin >> n >> m >> k;for (int i = 1; i <= k; i++){cin >> p[i].r >> p[i].c;p[i].id = i;}sort(p + 1, p + 1 + k, cmp1);vector<int>nxt(k + 2, inf);for (int i = k; i >= 1; i--){nxt[i] = min(nxt[i + 1], p[i].c);}int S = 0;int low = 0;for (int i = 1; i <= k; i++){S += (p[i].r - low) * (nxt[i] - 1);low = p[i].r;// cout << "i = " << i << " S = " << S << endl;}if (low < n) S += (n - low) * m;cout << S << endl;stack<int>st;for (int i = 1; i <= k; i++){if (!st.size()){st.push(i);}else{while (st.size() && p[i].c <= p[st.top()].c){st.pop();}st.push(i);}}vector<int>ans(k + 1, 0);while (st.size()){ans[p[st.top()].id] = 1;st.pop();}for (int i = 1; i <= k; i++){cout << ans[i] << " ";}cout << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}