和第一篇题解对照过,没有发现问题所在。
代码:
#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;
}