QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#522937#4236. Triangular LogsRngBasedWA 127ms34016kbC++203.9kb2024-08-17 17:05:302024-08-17 17:05:31

Judging History

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

  • [2024-08-17 17:05:31]
  • 评测
  • 测评结果:WA
  • 用时:127ms
  • 内存:34016kb
  • [2024-08-17 17:05:30]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define N 100015
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct lisan{
    vector<int> vt;
    void in(int x){ vt.emplace_back(x); }
    void build(){
        sort(all(vt));
        vt.resize(unique(all(vt)) - vt.begin());
    }
    int idx(int x){ return min((int)(lower_bound(all(vt), x) - vt.begin() + 1), (int)(vt.size())); }
}lx, ly;

vector<int> res;
vector<pii> all_tree[N];

struct segtree{
    struct segnode{
        int lch, rch, have;
    }seg[30 * N];
    int num = 0;
    int insert(int l, int r, int i, int p){
        int now = ++num;
        seg[now] = seg[i];
        if (l == r){
            seg[now].have++;
            return now;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) seg[now].lch = insert(l, mid, seg[i].lch, p);
        else seg[now].rch = insert(mid + 1, r, seg[i].rch, p);
        seg[now].have = seg[seg[now].lch].have + seg[seg[now].rch].have;
        return now;
    }
    int query(int l, int r, int i, int j, int ll, int rr){
        // cerr << l << " " << r << " " << i << " " << j << " " << ll << " " << rr << '\n';
        if (ll > rr) return 0;
        if (ll <= l && rr >= r)
            return seg[i].have - seg[j].have;
        int mid = (l + r) >> 1;
        if (rr <= mid) return query(l, mid, seg[i].lch, seg[j].lch, ll, rr);
        else if (ll > mid) return query(mid + 1, r, seg[i].rch, seg[j].rch, ll, rr);
        else return query(l, mid, seg[i].lch, seg[j].lch, ll, rr) +
                    query(mid + 1, r, seg[i].rch, seg[j].rch, ll, rr);
    }
    void brute(int l, int r, int i, int j, int ll, int rr, int x1, int x2){
        if (ll > rr) return;
        if (seg[i].have - seg[j].have == 0)
            return;
        if (l == r){
            auto it = lower_bound(all(all_tree[l]), pii(x1, 0));
            while (it != all_tree[l].end() && it->x <= x2)
                res.emplace_back(it->y), it = next(it);
            return;
        }
        int mid = (l + r) >> 1;
        if (ll <= mid) brute(l, mid, seg[i].lch, seg[j].lch, ll, rr, x1, x2);
        if (rr > mid) brute(mid + 1, r, seg[i].rch, seg[j].rch, ll, rr, x1, x2);
    }
}seg;

int n, m, k, q, version[N];
vector<pair<pii, int> > tree;
vector<pair<pii, pii> > query;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        int x, y, h;
        cin >> x >> y >> h;
        lx.in(x), ly.in(y);
        tree.emplace_back(pii(x, y), h);
    }
    lx.build(), ly.build();
    sort(all(tree));
    for (int i = 1; i <= n; i++){
        auto [_, c] = tree[i - 1];
        auto [x, y] = _;
        version[i] = seg.insert(1, n, version[i - 1], ly.idx(y));
        all_tree[ly.idx(y)].emplace_back(x, c);
    }

    for (int i = 1; i <= q; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int v1 = lower_bound(all(tree), pair<pii, int>(pii(x1, y1), 0)) - tree.begin();
        int v2 = lower_bound(all(tree), pair<pii, int>(pii(x2, y2), 1e9 + 5)) - tree.begin();
        assert(v1 <= v2);
        int have = seg.query(1, n, version[v2], version[v1], ly.idx(y1), ly.idx(y2));
        if (have >= 48)
            cout << 1 << '\n';
        else {
            bool tri = 0;
            res.clear();
            seg.brute(1, n, version[v2], version[v1], ly.idx(y1), ly.idx(y2), x1, x2);
            sort(all(res));
            for (int j = 2; j < res.size(); j++)
                if (res[j - 2] + res[j - 1] > res[j])
                    tri = 1;
            if (tri)
                cout << 1 << '\n';
            else cout << 0 << '\n';
        }
    }
}
/*
9 1
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 3 1 3
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7840kb

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: 1ms
memory: 5764kb

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: 0ms
memory: 5876kb

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: 88ms
memory: 32084kb

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: 83ms
memory: 31896kb

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: 126ms
memory: 33824kb

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: -100
Wrong Answer
time: 127ms
memory: 34016kb

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:

wrong answer 19279th lines differ - expected: '0', found: '1'