QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#522911#4236. Triangular LogsRngBasedTL 1ms5748kbC++203.6kb2024-08-17 16:43:542024-08-17 16:44:00

Judging History

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

  • [2024-08-17 16:44:00]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5748kb
  • [2024-08-17 16:43:54]
  • 提交

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 upper_bound(all(vt), x) - vt.begin(); }
}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){
        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 (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();
        int have = seg.query(1, n, version[v2], version[v1], y1, y2);
        if (have >= 32)
            cout << 1 << '\n';
        else {
            bool tri = 0;
            res.clear();
            seg.brute(1, n, version[v2], version[v1], y1, 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';
        }
    }
}

详细

Test #1:

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

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: -100
Time Limit Exceeded

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:


result: