求助,WA on #28
查看原帖
求助,WA on #28
535486
liqingming楼主2024/8/5 21:04

和第一篇题解对照过,没有发现问题所在。

代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 200010, INF = 2e9;
int n;
int len[3];

struct Cuboid
{
	int h, w, d;
} cuboid[N];
bool cmph(Cuboid A, Cuboid B)
{
	return A.h < B.h;
}
bool cmpw(Cuboid A, Cuboid B)
{
	return A.w < B.w;
}

unordered_map<int, int> p;
int idx;
int t[N];

int lowbit(int x)
{
	return x & -x;
}
void insert(int k, int x)
{
	for (int i = k; i <= idx; i += lowbit(i)) t[i] = min(t[i], x);
}
int query(int k)
{
	int res = INF;
	for (int i = k; i; i -= lowbit(i)) res = min(res, t[i]);
	return res;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++)
	{
		scanf("%d%d%d", &len[0], &len[1], &len[2]);
		sort(len, len + 3);
		cuboid[i] = {len[0], len[1], len[2]};
	}
	
	sort(cuboid + 1, cuboid + n + 1, cmpw);
	for (int i = 1; i <= n; i ++)
        if (cuboid[i - 1].w != cuboid[i].w)
            p[cuboid[i].w] = ++ idx;
	
	for (int i = 0; i <= idx; i ++) t[i] = INF;
	sort(cuboid + 1, cuboid + n + 1, cmph);
	
	for (int i = 1; i <= n;)
    {
        int l = i, r = i;
        while (r <= n && cuboid[l].h == cuboid[r].h) r ++;

        for (int j = l; j < r; j ++)
            if (query(p[cuboid[j].w] - 1) < cuboid[j].d)
            {
                puts("Yes");
                return 0;
            }
        for (int j = l; j < r; j ++) insert(p[cuboid[i].w], cuboid[i].d);
        i = r;
    }
	
	puts("No");
	
	return 0;
}
2024/8/5 21:04
加载中...