QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#61400 | #4236. Triangular Logs | 2pal1rak# | WA | 2ms | 25948kb | C++14 | 3.6kb | 2022-11-12 20:30:21 | 2022-11-12 20:30:23 |
Judging History
answer
#include <bits/stdc++.h>
#define mid ((st+dr)/2)
#define left_son (node<<1)
#define right_son ((node<<1)|1)
using namespace std;
const int Nmax = 1e5 + 5;
const int threshold = 50;
struct tree
{
int x, y, h;
} a[Nmax];
struct query
{
int xl, xh, yl, yh;
vector<int> v;
} b[Nmax];
vector<int> unique_xs, unique_ys;
map<int,int> xs, ys;
int currX;
int n, q, lim;
vector<pair<int, pair<int,int>>> events;
void normalize()
{
int i;
int nr = 0;
for(auto &it : ys)
{
it.second = ++nr;
unique_ys.push_back(it.first);
}
nr = 0;
for(auto &it : xs)
{
it.second = ++nr;
unique_xs.push_back(it.first);
}
for(i=1; i<=n; ++i)
{
a[i].x = xs[a[i].x];
a[i].y = ys[a[i].y];
}
for(i=1; i<=q; ++i)
{
b[i].xl = lower_bound(unique_xs.begin(), unique_xs.end(), b[i].xl) - unique_xs.begin() + 1;
b[i].xh = upper_bound(unique_xs.begin(), unique_xs.end(), b[i].xh) - unique_xs.begin();
b[i].yl = lower_bound(unique_ys.begin(), unique_ys.end(), b[i].yl) - unique_ys.begin() + 1;
b[i].yh = upper_bound(unique_ys.begin(), unique_ys.end(), b[i].yh) - unique_ys.begin();
}
}
class SegTree
{
vector<int> queries[Nmax<<3];
void do_update(vector<int> &v, int val)
{
vector<int> vv;
for(auto id : v)
if(currX <= b[id].xh) // still good
{
b[id].v.push_back(val);
if(b[id].v.size() < threshold)
{
vv.push_back(id);
}
}
v = vv;
}
public:
void add(int node, int st, int dr, int L, int R, int id)
{
if(st <= L && R <= dr)
{
queries[node].push_back(id);
return;
}
if(L <= mid) add(left_son, st, mid, L, R, id);
if(mid < R) add(right_son, mid+1, dr, L, R, id);
}
void update(int node, int st, int dr, int pos, int val)
{
do_update(queries[node], val);
if(st == dr) return;
if(pos <= mid) update(left_son, st, mid, pos, val);
else update(right_son, mid+1, dr, pos, val);
}
} aint;
bool get_result(vector<int> &v)
{
if(v.size() >= threshold) return 1;
sort(v.begin(), v.end());
int i;
for(i=0; i+2 < v.size(); ++i)
if(v[i] + v[i+1] > v[i+2]) return 1;
return 0;
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false); cin.tie(0);
cin >> n >> q;
int i;
for(i=1; i<=n; ++i)
{
cin >> a[i].x >> a[i].y >> a[i].h;
xs[a[i].x] = 1;
ys[a[i].y] = 1;
}
for(i=1; i<=q; ++i)
cin >> b[i].xl >> b[i].yl >> b[i].xh >> b[i].yh;
normalize();
for(i=1; i<=q; ++i)
{
events.push_back({ b[i].xl, {-1, i} });
events.push_back({ b[i].xh, {+1, i} });
}
for(i=1; i<=n; ++i)
{
events.push_back({ a[i].x, {0, i} });
}
sort(events.begin(), events.end());
lim = n;
for(auto it : events)
{
int tip = it.second.first;
int id = it.second.second;
currX = it.first;
if(tip == -1)
{
if(b[id].yl <= b[id].yh)
aint.add(1, 1, lim, b[id].yl, b[id].yh, id);
}
//if(tip == +1) aint.del(1, 1, lim, b[val].yl, b[val].yh, val);
if(tip == 0) aint.update(1, 1, lim, a[id].y, a[id].h);
}
for(i=1; i<=q; ++i)
cout << get_result(b[i].v) << '\n';
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 25948kb
input:
9 5 1 3 3 2 3 1 3 3 4 1 2 1 2 2 5 3 2 9 1 1 2 2 1 6 3 1 5 1 1 1 2 1 1 2 2 1 1 1 3 1 2 3 2 1 1 3 3
output:
0 1 0 1 1
result:
wrong answer 4th lines differ - expected: '0', found: '1'