首页 > 其他分享 >AtCoder备赛刷题 ABC 361 | Go Territory

AtCoder备赛刷题 ABC 361 | Go Territory

时间:2025-01-06 13:01:32浏览次数:15  
标签:AtCoder Territory nxt int pos Sample add ABC now

学习C++从娃娃抓起!记录下AtCoder(日本算法竞技网站)备赛学习过程中的题目,记录每一个瞬间。

附上汇总贴:AtCoder 备赛刷题 | 汇总


【Problem Statement】

There are N N N stones placed on a 2 2 2-dimensional plane. The i i i-th stone is located at coordinates ( X i , Y i ) (X_i,Y_i) (Xi​,Yi​). All stones are located at lattice points in the first quadrant (including the axes).

有 N N N 块石头放置在一个 2 2 2 维的平面上。第 i i i 块石头位于坐标 ( X i , Y i ) (X_i,Y_i) (Xi​,Yi​) 处。所有石头都位于第一象限(包括轴线)的格点处。

Count the number of lattice points ( x , y ) (x,y) (x,y) where no stone is placed and it is impossible to reach ( − 1 , − 1 ) (−1,−1) (−1,−1) from ( x , y ) (x,y) (x,y) by repeatedly moving up, down, left, or right by 1 1 1 without passing through coordinates where a stone is placed.

计算没有放置石头的格子点 ( x , y ) (x,y) (x,y) 的数量,并且通过反复向上、向下、向左或向右移动 1 1 1 而不通过放置石头的坐标,不可能从 ( x , y ) (x,y) (x,y) 到达 ( − 1 , − 1 ) (-1,-1) (−1,−1)。

More precisely, count the number of lattice points ( x , y ) (x,y) (x,y) where no stone is placed, and there does not exist a finite sequence of integer pairs ( x 0 , y 0 ) , … , ( x k , y k ) (x_0,y_0),…,(x_k,y_k) (x0​,y0​),…,(xk​,yk​) that satisfies all of the following four conditions:

更准确地说,计算没有放置石头的格点 ( x , y ) (x,y) (x,y) 的数量,并且不存在满足以下四个条件的整数对 ( x 0 , y 0 ) , … , ( x k , y k ) (x_0,y_0),…,(x_k,y_k) (x0​,y0​),…,(xk​,yk​) 的有限序列:

  • ( x 0 , y 0 ) = ( x , y ) (x_0,y_0)=(x,y) (x0​,y0​)=(x,y).
  • ( x k , y k ) = ( − 1 , − 1 ) (x_k,y_k)=(−1,−1) (xk​,yk​)=(−1,−1).
  • ∣ x i − x i + 1 ∣ + ∣ y i − y i + 1 ∣ = 1 |x_i−x_i+1|+|y_i−y_i+1|=1 ∣xi​−xi​+1∣+∣yi​−yi​+1∣=1 for all 0 ≤ i < k 0≤i<k 0≤i<k.
  • There is no stone at ( x i , y i ) (x_i,y_i) (xi​,yi​) for all 0 ≤ i ≤ k 0≤i≤k 0≤i≤k.

【Constraints】

  • 0 ≤ N ≤ 2 × 1 0 5 0≤N≤2×10^5 0≤N≤2×105
  • 0 ≤ X i , Y i ≤ 2 × 1 0 5 0≤X_i,Y_i≤2×10^5 0≤Xi​,Yi​≤2×105
  • The pairs ( X i , Y i ) (X_i,Y_i) (Xi​,Yi​) are distinct.
  • All input values are integers.

【Input】

The input is given from Standard Input in the following format:

N
X_1 Y_1
.
.
.
X_N Y_N

【Output】

Print the number of lattice points that satisfy the conditions.

【Sample Input 1】

5
1 0
0 1
2 3
1 2
2 1

【Sample Output 1】

1

It is impossible to reach ( − 1 , − 1 ) (−1,−1) (−1,−1) from ( 1 , 1 ) (1,1) (1,1).

在这里插入图片描述

【Sample Input 2】

0

【Sample Output 2】

0

【Sample Input 3】

22
0 1
0 2
0 3
1 0
1 4
2 0
2 2
2 4
3 0
3 1
3 2
3 4
5 1
5 2
5 3
6 0
6 4
7 0
7 4
8 1
8 2
8 3

【Sample Output 3】

6

There are six such points: ( 6 , 1 ) , ( 6 , 2 ) , ( 6 , 3 ) , ( 7 , 1 ) , ( 7 , 2 ) , ( 7 , 3 ) (6,1),(6,2),(6,3),(7,1),(7,2),(7,3) (6,1),(6,2),(6,3),(7,1),(7,2),(7,3).

在这里插入图片描述

【代码详解】

《AtCoder Go Territory》 #并查集# #双指针two-pointer#

#include <bits/stdc++.h>
using namespace std;
const int N = 200200, M=N<<3;
typedef pair<int, int> PII;
PII p[N];
vector<pair<int, int> > l[N];
int n, sz[M];
int h[M], e[M], ne[M], idx;
bool vis[M];
queue<int> q;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main()
{
    cin >> n;
    int MX=0, MY=0;
    int x, y;
    memset(h, -1, sizeof(h));
    for (int i=1; i<=n; i++)
    {
        cin >> x >> y;
        x = x+1, y = y+1;
        p[i] = make_pair(x, y);
        MX = max(MX, x);
        MY = max(MY, y);
    }
    MX++; MY++;
    sort(p+1, p+n+1);
    for (int i=0, L=0; i<=MX; i++)
    {
        int R = L;
        while (R+1<=N && p[R+1].first==i) ++R;
        int Low = 0;
        for (int j=L+1; j<=R; j++)
        {
            if (Low<p[j].second) l[i].push_back(make_pair(Low, p[j].second-1));
            Low = p[j].second+1;
        }
        l[i].push_back(make_pair(Low, MY));
        L = R;
    }
    int tot = 1;
    for (int i=0; i<MX; i++)
    {
        int len = l[i].size();
        int nxtlen = l[i+1].size();
        for (int j=0,pos=0; j<len; j++)
        {
            int now = tot+j;
            int L=l[i][j].first, R=l[i][j].second;
            sz[now] = R-L+1;
            while (pos<nxtlen && l[i+1][pos].second<L) ++pos;
            while (pos<nxtlen && l[i+1][pos].second<=R)
            {
                int nxt = tot + len + pos;
                add(now, nxt); 
                add(nxt, now);
                ++pos;
            }
            if (pos<nxtlen && l[i+1][pos].first<=R)
            {
                int nxt = tot+len+pos;
                add(now, nxt); 
                add(nxt, now);
            }
        }
        tot +=len;
    }
    q.push(1);
    vis[1] = true;
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i=h[u]; i!=-1; i=ne[i])
        {
            int j = e[i];
            // cout << j << " " << vis[j] << endl;
            if (vis[j]) continue;
            vis[j] = true;
            q.push(j);
        }
    }
    long long ans = 0;
    for (int i=1; i<=tot; i++)
        if (!vis[i]) ans += sz[i];
    cout << ans;
    return 0;
}

【运行结果】

5
1 0
0 1
2 3
1 2
2 1
1

标签:AtCoder,Territory,nxt,int,pos,Sample,add,ABC,now
From: https://blog.csdn.net/guolianggsta/article/details/144891471

相关文章