列表

详情

NC202138. Mr. Panda and Dominoes

描述

Mr. Panda likes creating and solving mathematical puzzles. One day, Mr. Panda came up with a puzzle when he was playing dominoes.In a grid that consists of an infinite number of rows and columns, all cells are white except given cells which are colored black. Mr. Panda wants to know how many dominoes there are in the gird.A domino is a rectangle that meets the following requirements.
For example, in the chart below, the grid on the left contains dominos ( dominos of and dominos of ), and the grid on the right contains dominos ( dominos of , 4 dominos of and a domino of ).

Because the grid is huge, Mr. Panda is too lazy to count the number of dominoes. Could you please help Mr. Panda find how many dominoes there are in the gird?

输入描述

The first line of input gives the number of test cases, .  test cases follow.
Each test case starts with a line consists of an integer - , the number of black cells in the gird.
Then,  lines follow. Each line consists of  integers  and , indicating row and column of a black cell in the grid.



 over all test cases
For each test, no two black cells are in the same position

输出描述

For each test case, output one line containing ``Case #x: y'', where x is the test case number (starting from 1) and y is the number of dominos that Mr. Panda wants to know for the i-th input data set.

示例1

输入: 

2
7
1 1
1 2
1 3
2 2
3 1
3 2
3 3
14
1 1
1 2
1 3
1 4
1 5
1 6
2 1
2 6
3 1
3 2
3 3
3 4
3 5
3 6

输出: 

Case #1: 6
Case #2: 15

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 8368ms, 内存消耗: 78776K, 提交时间: 2022-08-30 20:15:29 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;

const int N = 1000007 * 2;
const int MAX = 1000000000;
 
int n;
pair<int, int> cells[N];
 
pair<int, int> rotate90(const pair<int, int>& cell) {
    return {MAX - cell.second + 1, cell.first};
}
 
int lenRight[N], lenDown[N];
int lenLeft[N], lenUp[N];
int cords[N], cordPos[N];
 
tuple<int, int, int, int> events[N * 3];
 
enum EventCategory { IN = 0, QUERY = 1, OUT = 2 };
 
int val[N];
 
void add(int x, int delta, int maxX) {
    ++x;
    while (x <= maxX + 10) {
        val[x] += delta;
        x += x & -x;
    }
}
 
int getSum(int x) {
    ++x;
    int sum = 0;
    while (x) {
        sum += val[x];
        x -= x & -x;
    }
    return sum;
}
 
int intervalSum(int left, int right) {
    return getSum(right) - getSum(left - 1);
}
 
LL go() {
    sort(cells, cells + n);
 
    int downAt = n - 1;
    for (int i = n - 1; i >= 0; --i) {
        lenRight[i] = lenUp[i] = 1;
        if (i + 1 < n && cells[i + 1].first == cells[i].first && cells[i + 1].second == cells[i].second + 1) {
            lenRight[i] += lenRight[i + 1];
        }
        while (downAt > i && (cells[downAt].first > cells[i].first + 1 || (cells[downAt].first == cells[i].first + 1 && cells[downAt].second > cells[i].second))) {
            --downAt;
        }
        if (cells[downAt].first == cells[i].first + 1 && cells[downAt].second == cells[i].second) {
            lenUp[i] += lenUp[downAt];
        }
    }
 
    int upAt = 0;
    for (int i = 0; i < n; ++i) {
        lenLeft[i] = lenDown[i] = 1;
        if (i > 0 && cells[i - 1].first == cells[i].first && cells[i - 1].second + 1 == cells[i].second) {
            lenLeft[i] += lenLeft[i - 1];
        }
        while (upAt < i && (cells[upAt].first < cells[i].first - 1 || (cells[upAt].first == cells[i].first - 1 && cells[upAt].second < cells[i].second))) {
            ++upAt;
        }
        if (cells[upAt].first == cells[i].first - 1 && cells[upAt].second == cells[i].second) {
            lenDown[i] += lenDown[upAt];
        }
    }
 
    for (int i = 0; i < n; ++i) {
        cords[i] = cells[i].first;
        {
            int at = cells[i].second - cells[i].first * 2;
            events[i * 3] = make_tuple(at, cells[i].first, QUERY, i);
        }
        {
            int at = cells[i].second - cells[i].first * 2 + 1;
            int radius = min(lenUp[i], lenRight[i] >> 1);
            events[i * 3 + 1] = make_tuple(at, cells[i].first, IN, i);
            events[i * 3 + 2] = make_tuple(at, cells[i].first + radius - 1, OUT, i);
        }
    }
 
    int numCords = n;
    sort(cords, cords + numCords);
    numCords = unique(cords, cords + numCords) - cords;
 
    for (int i = 0; i < n; ++i) {
        cordPos[i] = lower_bound(cords, cords + numCords, cells[i].first) - cords;
    }
 
    int numEvents = 3 * n;
    sort(events, events + numEvents);
 
    LL ans = 0;
    for (int i = 0; i < numEvents; ++i) {
        int x = get<3>(events[i]);
        // cout << "bucket = " << get<0>(events[i]) << " category = " << get<1>(events[i]) << " x = " << cells[x].first << " y = " <<  cells[x].second << endl;
        switch (get<2>(events[i])) {
            case IN: {
                int at = cordPos[x];
                assert(at < numCords);
                add(at, 1, numCords);
                break;
            }
            case OUT: {
                int at = cordPos[x];
                assert(at < numCords);
                add(at, -1, numCords);
                break;
            }
            case QUERY: {
                int high = cordPos[x];
                int radius = min(lenDown[x], lenLeft[x] >> 1);
                int low = lower_bound(cords, cords + numCords, cells[x].first - radius + 1) - cords;
                ans += intervalSum(low, high);
                // cout << intervalSum(low, high) << endl;
                break;
            }
        }
    }
    // cout << "ans is " << ans << endl;
    return ans;
}
 
void solve(int caseNumber) {
    cin>>n;
    for (int i = 0; i < n; ++i) cin >> cells[i].first >> cells[i].second;
    LL ans = go();
    for (int i = 0; i < n; ++i) {
        cells[i] = rotate90(cells[i]);
    }
    ans += go();
 
    cout << "Case #" << caseNumber << ": " << ans << endl;
}
 
int main() {
    int numCases;
    cin >> numCases;
    for (int caseNumber = 1; caseNumber <= numCases; ++caseNumber) {
        solve(caseNumber);
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 10670ms, 内存消耗: 43752K, 提交时间: 2020-02-21 03:21:48 

//#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<tuple>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define lastu (get<2>(z[lastj]))
#define nowu (get<2>(z[nowj]))
using namespace std;
using namespace __gnu_pbds;
typedef tuple<int,int,int> tdata;
const int N=1000005;
int T,n,x[N],y[N],L[N],R[N],U[N],D[N],Far[N],Pos[N],LastL,LastR,NowL,NowR,IndexLast,IndexNow;;
tdata z[N];
 
struct farless {bool operator()(const int& x,const int& y)const{return Far[x]<Far[y]||Far[x]==Far[y]&&x<y;}};
struct posless {bool operator()(const int& x,const int& y)const{return Pos[x]<Pos[y]||Pos[x]==Pos[y]&&x<y;}};
tree<int,null_type,farless,rb_tree_tag,tree_order_statistics_node_update> FarTree;
tree<int,null_type,posless,rb_tree_tag,tree_order_statistics_node_update> PosTree;


inline int getv(const tdata u){return get<1>(u)-get<0>(u)*2;}

inline int sum(int t){Pos[0]=t;return PosTree.size()-PosTree.order_of_key(0);}

long long Count(int* x,int* y){
    register int i,Cnt=0;
    for(i=1;i<=n;++i)L[i]=R[i]=U[i]=D[i]=1;
    for(i=1;i<=n;++i)z[i]=make_tuple(x[i],y[i],i);
    sort(z+1,z+n+1,[](tdata a,tdata b){return get<0>(a)!=get<0>(b)?get<0>(a)<get<0>(b):get<1>(a)<get<1>(b);});
    for(i=2;i<=n;++i)
        if(get<0>(z[i])==get<0>(z[i-1])&&get<1>(z[i])==get<1>(z[i-1])+1)
            L[get<2>(z[i])]=L[get<2>(z[i-1])]+1;
    for(i=n-1;i>0;--i)
        if(get<0>(z[i])==get<0>(z[i+1])&&get<1>(z[i])==get<1>(z[i+1])-1)
            R[get<2>(z[i])]=R[get<2>(z[i+1])]+1;
    sort(z+1,z+n+1,[](tdata a,tdata b){return get<1>(a)!=get<1>(b)?get<1>(a)<get<1>(b):get<0>(a)<get<0>(b);});
    for(i=2;i<=n;++i)
        if(get<1>(z[i])==get<1>(z[i-1])&&get<0>(z[i])==get<0>(z[i-1])+1)
            U[get<2>(z[i])]=U[get<2>(z[i-1])]+1;
    for(i=n-1;i>0;--i)
        if(get<1>(z[i])==get<1>(z[i+1])&&get<0>(z[i])==get<0>(z[i+1])-1)
            D[get<2>(z[i])]=D[get<2>(z[i+1])]+1;
    sort(z+1,z+n+1,[](tdata a,tdata b){return getv(a)!=getv(b)?getv(a)<getv(b):get<0>(a)<get<0>(b);});
    FarTree.clear();PosTree.clear();
    IndexLast=IndexNow=0x7f7f7f7f;
    LastL=NowL=1;LastR=NowR=0;
    z[n+1]=make_tuple(0x7f7f7f7f,0,n+1);
    for(i=1;i<=n+1;++i){
        int u=get<2>(z[i]);
        Far[u]=min(R[u]>>1,D[u]);Far[u]=Far[u]==0?-1:x[u]+Far[u]-1;
        Pos[u]=x[u];
        if(getv(z[i])!=getv(z[i-1])){
            FarTree.clear();PosTree.clear();
            for(int lastj=LastL,nowj=NowL;nowj<=NowR;++nowj){
                while(lastj<=LastR&&Pos[lastu]<=Pos[nowu]){
                    if(Far[lastu]!=-1&&Far[lastu]>=Pos[nowu])
                        FarTree.insert(lastu),PosTree.insert(lastu);
                    ++lastj;
                }
                while(FarTree.size()>0){
                    int v=*FarTree.begin();
                    if(Far[v]<Pos[nowu])FarTree.erase(v),PosTree.erase(v);else break;
                }
                int w=min(L[nowu]>>1,U[nowu]);
                if(w>0)Cnt+=sum(Pos[nowu]+1-w);
            }
            LastL=NowL;LastR=NowR;
            NowL=NowR=i;
            IndexLast=IndexNow;IndexNow=getv(z[i]);
        }
        else NowR=i;
    }
    return Cnt;
}
 
long long Solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
    return Count(x,y)+Count(y,x);
}
 
int main(){
    scanf("%d",&T);
    for(int _T=1;_T<=T;++_T)printf("Case #%d: %lld\n",_T,Solve());
}

C++(clang++11) 解法, 执行用时: 11950ms, 内存消耗: 89956K, 提交时间: 2021-04-22 14:43:19 

#include<bits/stdc++.h> 
using namespace std;
const int N=5000010;
int n;
struct node
{
	int x,y,i;
	friend bool operator < (node a,node b)
	{
		return a.x==b.x?a.y<b.y:a.x<b.x;
	}
}o[N];
int maxx[N],maxy[N],xi[N],ix[N],yi[N],iy[N];
bool cmpx(node a,node b)
{
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
bool cmpy(node a,node b)
{
	return a.y==b.y?a.x<b.x:a.y<b.y;
}
bool cmpi(node a,node b)
{
	return a.i<b.i;
}
int main()
{
	int T,k,n;scanf("%d",&T);
	for(k=1;k<=T;k++)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d%d",&o[i].x,&o[i].y),o[i].i=i;
		o[n+1].x=0;
		o[n+1].y=0;
		o[n+1].i=0;
		sort(o+1,o+1+n,cmpx);
		for(int i=n;i;i--)
		{
			xi[i]=o[i].i;
			ix[o[i].i]=i;
			if(o[i].x==o[i+1].x&&o[i].y==o[i+1].y-1)
				maxy[o[i].i]=maxy[o[i+1].i]+1;
			else
				maxy[o[i].i]=1;
		}
		sort(o+1,o+1+n,cmpy);
		for(int i=n;i;i--)
		{
			yi[i]=o[i].i;
			iy[o[i].i]=i;
			if(o[i].y==o[i+1].y&&o[i].x==o[i+1].x-1)
				maxx[o[i].i]=maxx[o[i+1].i]+1;
			else
				maxx[o[i].i]=1;
		}
		sort(o+1,o+1+n,cmpi);
		int ans=0;
		for(int i=1;i<=n;i++)//1*2 
		{
			int a=maxx[i],b=maxy[i];
			for(int xx=1,yy=2;xx<=a&&yy<=b;xx++,yy+=2)
				if(maxy[yi[iy[i]+xx-1]]>=yy&&maxx[xi[ix[i]+yy-1]]>=xx)
					ans++;
			for(int xx=2,yy=1;xx<=a&&yy<=b;xx+=2,yy++)
				if(maxy[yi[iy[i]+xx-1]]>=yy&&maxx[xi[ix[i]+yy-1]]>=xx)
					ans++;
		}
		printf("Case #%d: %d\n",k,ans); 
		
	}
}

上一题

© 2024 nowcoder.com