QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#394131 | #4236. Triangular Logs | MHo2005 | TL | 1095ms | 55004kb | C++20 | 3.9kb | 2024-04-20 04:28:54 | 2024-04-20 04:28:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define ff first
#define ss second
const int maxn = 3e5 + 10;
int ans[maxn], thres = 45, n, q, cnt = 0;
ii pre[maxn];
struct tree {
int x, y, h;
} t[maxn];
struct queries {
int x1, y1, x2, y2, id;
} qu[maxn];
struct sweep {
int x, y, type, h;
} sw[maxn];
vector<int> cy, tmp, fen[maxn];
vector<ii> seg[4*maxn];
inline void upd(int pos, int val) {for (; pos<maxn; pos+=pos&-pos) fen[pos].push_back(val);}
inline int ask(int pos, int l, int r)
{
int ans = 0;
for (; pos; pos-=pos&-pos)
ans += upper_bound(fen[pos].begin(), fen[pos].end(), r) - lower_bound(fen[pos].begin(), fen[pos].end(), l);
return ans;
}
inline int ask(int lx, int rx, int l, int r) {return ask(rx, l, r) - ask(lx-1, l, r);}
void build(int id = 1, int l = 1, int r = cnt)
{
if (l == r)
{
if (!sw[l].type) seg[id].push_back({sw[l].y, sw[l].h});
return;
}
int m = (l+r)>>1;
build(id<<1, l, m);
build(id<<1|1, m+1, r);
merge(seg[id<<1].begin(), seg[id<<1].end(), seg[id<<1|1].begin(), seg[id<<1|1].end(),
back_inserter(seg[id]));
}
void query(int id, int cl, int cr, int lx, int rx, int l, int r)
{
if (cl > rx || cr < lx) return;
if (cl >= lx && cr <= rx)
{
if (seg[id].empty()) return;
ii temp = {l, 0};
auto pos1 = lower_bound(seg[id].begin(), seg[id].end(), temp);
temp = {r, 2e9};
auto pos2 = upper_bound(seg[id].begin(), seg[id].end(), temp);
while (pos1 != pos2) tmp.push_back(pos1->ss), pos1++;
return;
}
int m = (cl + cr) >> 1;
query(id<<1, cl, m, lx, rx, l, r);
query(id<<1|1, m+1, cr, lx, rx, l, r);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen("input.in", "r")) {
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
}
cin>>n>>q;
for (int i=1; i<=n; i++)
{
cin>>t[i].x>>t[i].y>>t[i].h;
cy.push_back(t[i].y);
}
for (int i=1; i<=q; i++)
{
cin>>qu[i].x1>>qu[i].y1>>qu[i].x2>>qu[i].y2;
qu[i].id = i;
cy.push_back(qu[i].y1);
cy.push_back(qu[i].y2);
}
sort(cy.begin(), cy.end());
cy.resize(unique(cy.begin(), cy.end()) - cy.begin());
for (int i=1; i<=n; i++)
{
t[i].y = lower_bound(cy.begin(), cy.end(), t[i].y) - cy.begin() + 1;
sw[++cnt] = {t[i].x, t[i].y, 0, t[i].h};
}
for (int i=1; i<=q; i++)
{
qu[i].y1 = lower_bound(cy.begin(), cy.end(), qu[i].y1) - cy.begin() + 1;
qu[i].y2 = lower_bound(cy.begin(), cy.end(), qu[i].y2) - cy.begin() + 1;
sw[++cnt] = {qu[i].x1, qu[i].y1, -i, 0};
sw[++cnt] = {qu[i].x2, qu[i].y2, i, 0};
}
sort(sw+1, sw+cnt+1, [](sweep x, sweep y) {return (x.x != y.x ? x.x < y.x : x.type < y.type);});
// for (int i=1; i<=cnt; i++) if (!sw[i].type) upd(i, sw[i].y);
// for (int i=1; i<maxn; i++) sort(fen[i].begin(), fen[i].end());
build();
for (int i=1; i<=cnt; i++) if (sw[i].type)
{
if (sw[i].type < 0) pre[-sw[i].type] = {i, sw[i].y};
else
{
int cnt_tree = ask(pre[sw[i].type].ff, i, pre[sw[i].type].ss, sw[i].y);
if (cnt_tree >= thres) ans[sw[i].type] = 1;
else
{
tmp.clear();
query(1, 1, cnt, pre[sw[i].type].ff, i, pre[sw[i].type].ss, sw[i].y);
sort(tmp.begin(), tmp.end());
bool f = 0;
if (tmp.size() >= 3)
for (int i=0; i<tmp.size()-2; i++) if (tmp[i] + tmp[i+1] > tmp[i+2])
{
f = 1;
break;
}
ans[sw[i].type] = f;
}
}
}
for (int i=1; i<=q; i++) cout<<ans[i]<<"\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9852kb
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 0 1
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 9932kb
input:
481 1 8 6788 8975 24 6552 2668 26 7948 4730 40 531 9805 110 1914 1916 164 7073 3371 165 6293 7756 170 9946 2003 179 9654 1700 215 6447 2229 221 3149 3030 242 1999 6843 242 5764 3163 249 3716 8634 250 6801 9317 260 2741 4273 282 5436 4836 284 3951 6483 288 4812 76 375 9004 5492 380 5627 5929 391 6385...
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 3ms
memory: 11968kb
input:
378 1 62730 50925 80731 92666 77280 61521 29236 67032 7889 35986 96802 8763 13313 49918 83582 51842 66775 47834 2286 12925 41106 39790 6698 15243 65145 56379 68496 35570 809 525 39834 16723 48002 77230 16273 16032 52615 7621 77300 92267 82517 39917 13170 89084 77751 45638 23868 49631 7758 71381 5191...
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 147ms
memory: 52972kb
input:
100000 100000 299999993 206450345 26023928 334281171 300000008 18107965 318653732 299999990 82338399 299999997 393028366 37212808 299999992 208114125 82126189 300000002 303613195 34463905 270033576 299999993 49200970 300000003 249755524 5829381 300000003 367329175 12867359 300000009 337452692 131045...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #5:
score: 0
Accepted
time: 1095ms
memory: 50508kb
input:
100000 100000 299999990 299999990 40343876 299999990 299999991 75128878 299999990 299999992 54630219 299999990 299999993 2733654 299999990 299999994 46236519 299999990 299999995 98430004 299999990 299999996 48355189 299999990 299999997 85287882 299999990 299999998 83938086 299999990 299999999 739070...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #6:
score: 0
Accepted
time: 168ms
memory: 54316kb
input:
100000 100000 586649484 999402721 770254678 406977522 613559 332964690 987164 445493717 518079399 249557488 999424331 597100212 143514230 999205612 56986976 933588533 509797 769263555 696911 930171165 201130067 833170 541105172 912457971 145501 423684829 612968794 999276416 167526939 136454621 70428...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #7:
score: 0
Accepted
time: 215ms
memory: 55004kb
input:
100000 100000 341071 873501571 1101 59980263 526804 9 297715277 999186682 197674 709891830 999005915 346 999712634 250379232 3158 999959502 879534904 11273 253455643 999864444 49222 427866822 999577133 210191465 729566332 999548170 14 657471525 144302 846059 319542083 999756032 6275 219750473 765955...
output:
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 ...
result:
ok 100000 lines
Test #8:
score: -100
Time Limit Exceeded
input:
100000 100000 330451877 499036874 19421 148915905 333179772 5692 556747855 500052531 51199 580265032 499999972 188350435 380806313 500000128 65 500046272 499999847 2336904 496578778 500015254 22900850 499999993 473970765 17403806 499999989 499163205 2 499999946 499999562 19056 671553596 327120722 53...