Why WA on #5?
查看原帖
Why WA on #5?
385165
ZeroF楼主2024/3/25 20:57

rt

// By 0x0F
#include <bits/stdc++.h>
//#define AT_contest
#ifdef AT_contest
#include <atcoder/all>
using namespace atcoder;
#endif

using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define mpii map<int, int>
#define vi vector<int>
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}
#define inf 0x7fffffff
#define INF 0x3f3f3f3f3f3f3f3fll
#if defined(int)
#define RETURN_MAIN signed
#endif
#if !defined(int)
#define RETURN_MAIN int
#endif

struct WWW{
    int l,r; //左右端点
    long long sum; //维护总和
}tree[400010];
void pushup(int p){
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void build(int p,int l,int r){
    tree[p].l=l,tree[p].r=r; //当前树的管理区间范围
    if(l==r){
        return;
    }
    int mid=(l+r)/2; //区间中点
    build(p*2,l,mid); //递归建左子树
    build(p*2+1,mid+1,r); //递归建右子树
    pushup(p); //回传sum
}
void modify(int p,int x,int k){
    if(tree[p].l==tree[p].r){ //要修改的节点
        tree[p].sum+=k; //直接修改,返回
        return;
    }
    int mid=(tree[p].l+tree[p].r)/2;
    if(x<=mid)modify(p*2,x,k); //在左子树,递归到左边
    if(x>mid)modify(p*2+1,x,k); //在右子树,递归到右边
    pushup(p); //回传sum
}
long long query(int p,int l,int r){
    if(tree[p].l>=l&&tree[p].r<=r){ //在查询区间内
        return tree[p].sum; //直接返回值
    }
    long long ans=0;
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)ans+=query(p*2,l,r); //如果左子树区间有重叠部分,答案加上左边的查询
    if(r>mid)ans+=query(p*2+1,l,r); ////如果右子树区间有重叠部分,答案加上右边的查询
    return ans;
}

struct Node {
    int l, r;
    Node() {l = inf, r = -1;}
} hl[1000010], vl[1000010];
priority_queue<int, vi, greater<int> > qh, qv;
int toth = 1, totv = 1, n, m, hdh[100010], hdv[100010];
bool vis1[1000010], vis2[1000010];
vector<pii> oper[100010];
RETURN_MAIN main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        int x = read(), l = read(), r = read();
        hl[x].l = min(hl[x].l, l), hl[x].r = max(hl[x].r, r);
        if(!vis1[x]) qh.push(x), vis1[x] = 1;
    }
    for (int i = 1; i <= m; i++) {
        int y = read(), l = read(), r = read();
        vl[y].l = min(vl[y].l, l), vl[y].r = max(vl[y].r, r);
        if (!vis2[y]) qv.push(y), vis2[y] = 1;
    }
    hl[0].l = hl[1000000].l = 0, hl[0].r = hl[1000000].r = 1000000;
    vl[0].l = vl[1000000].l = 0, vl[0].r = vl[1000000].r = 1000000;
    for (int i = 1; i <= n; i++) hdh[++toth] = qh.top(), qh.pop();
    for (int i = 1; i <= m; i++) hdv[++totv] = qv.top(), qv.pop();
    hdh[1] = hdv[1] = 0;
    hdh[++toth] = hdv[++totv] = 1000000;
    for (int i = 1; i <= toth; i++) {
        int st = lower_bound(hdv + 1, hdv + totv + 1, hl[hdh[i]].l) - hdv,
            ed = upper_bound(hdv + 1, hdv + totv + 1, hl[hdh[i]].r) - hdv - 1;
        if (st > ed) continue;
        oper[st].pb({i, 1}), oper[ed].pb({i, -1});
    }
    build(1, 1, 100005);
    int ans = 0;
    for (int i = 1; i <= totv; i++) {
        int st = lower_bound(hdh + 1, hdh + toth + 1, vl[hdv[i]].l) - hdh,
            ed = upper_bound(hdh + 1, hdh + toth + 1, vl[hdv[i]].r) - hdh - 1;
        if (st > ed) continue;
        int tmp = query(1, st, ed);
        if (tmp > 0) ans += tmp - 1;
        for (auto j : oper[i]) modify(1, j.fi, j.se);
    }
    printf("%d", ans);
    return 0;
}
2024/3/25 20:57
加载中...