QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#394130#4236. Triangular LogsMHo2005RE 3ms3800kbC++203.8kb2024-04-20 04:27:152024-04-20 04:27:16

Judging History

你现在查看的是最新测评结果

  • [2024-04-20 04:27:16]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:3800kb
  • [2024-04-20 04:27:15]
  • 提交

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 = 0;
            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;
                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: 2ms
memory: 3704kb

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: 3800kb

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: 2ms
memory: 3772kb

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: -100
Runtime Error

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:


result: