CF 1980 F1 Field Division (easy version) (*1900)

CF 1980 F1 Field Division (easy version) (*1900)

题目链接

题意：

有一个大小为 \(n \times m\) （$2 \le n,m\le 10^9 $）的矩形。其中有 \(k\) 个喷泉，你现在可以从左侧或者上侧任意一个不是喷泉的单元格出发，每次只能移向相邻的下或者右的单元格。直到走到矩阵的右侧或者底侧结束。并且中途不能经过任何一个喷泉。走过的路径将整个矩阵分成了两个部分。请你求出左下这一部分的面积最大值（包含走过的单元格）。并且回答对于每个喷泉，如果允许经过，面积是否会增大。

思路：

显然，我们每次都贴着喷泉去走，面积才会最大。我们可以把面积根据喷泉的位置划分成一段一段来求解。

容易发现只有后面的喷泉的横坐标大于前面的横坐标才会拐弯。那么我们可以维护每一列的最大横坐标。

按照纵坐标顺序枚举所有喷泉的纵坐标计算即可。因为范围很大，那么用map维护即可。

接着看第二个问题，我们发现只有满足当前喷泉的横坐标是当前列的横坐标最大值并且大于前一个喷泉对应的

最大横坐标即可。这里开了一个st数组来维护前一个喷泉对应的最大横坐标。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;

void Showball(){
   int n,m,k;
   cin>>n>>m>>k;
   vector<PII> a(k+1);
   map<int,int> rmax;
   vector<int> col;
   for(int i=1;i<=k;i++){
      int x,y;
      cin>>x>>y;
      a[i]={x,y};
      col.pb(y);
      rmax[y]=max(rmax[y],x);
   }
   sort(all(col));
   int len=unique(all(col))-col.begin();
   LL ans=0;
   int cur=0;
   map<int,int> st;
   int pre=1;
   for(int i=0;i<len;i++){
      int y=col[i];
      ans+=1LL*(y-pre)*(n-cur);
      st[y]=cur;
      cur=max(cur,rmax[y]);
      pre=y;
   }
   ans+=1LL*(m-pre+1)*(n-cur);
   cout<<ans<<endl;
   for(int i=1;i<=k;i++){
      auto [x,y]=a[i];
      if(x==rmax[y]&&x>st[y]) cout<<"1 ";
      else cout<<"0 ";
   }
   cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}