求助:开O2AC,不开全WA
  • 板块P1904 天际线
  • 楼主golemon
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/25 22:11
  • 上次更新2023/11/3 01:11:46
查看原帖
求助:开O2AC,不开全WA
648005
golemon楼主2023/8/25 22:11
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;

// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second

typedef long long LL;
#define int long long 
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 21;
int w[N];
int n;
struct Segment { // 线段
    int x, y1, y2;
    int k;
    // 按横坐标进行排序
    bool operator<(const Segment& rhs) const {
        return x < rhs.x;
    }
}seg[N << 1];
vector<int> native;
int find(int y) {
    return lower_bound(all(native), y) - native.begin();
}
struct SegTree {
    int l,r,cnt;
    int len;
}tr[N << 3];
inline int ls(int u) {return u << 1; }
inline int rs(int u) {return u << 1 | 1; }
void pushup(int u) {
    if(tr[u].cnt) tr[u].len = (native[tr[u].r + 1] - native[tr[u].l]);
    else if(tr[u].l != tr[u].r) {
        tr[u].len = tr[ls(u)].len + tr[rs(u)].len;
    } else tr[u].len = 0;
}
void build(int u, int l, int r) {
    if(l == r) tr[u] = {l,r,0,0};
    else {
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(ls(u),l,mid), build(rs(u),mid+1,r);
    }
}
void modify(int u, int l, int r, int k) {
    if(tr[u].l >= l && tr[u].r <= r) {
        tr[u].cnt += k;
        pushup(u);
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(ls(u), l,r,k);
        if(r > mid) modify(rs(u), l,r,k);
        pushup(u);
    }
}
// int T = 1;
void inpfile();
PII res[N];
void solve() {
    native.clear();
    int seglen = 0;
    // cin>>n;
    int x1,y2,x2;
    // int n = 0;
    while(~scanf("%d%d%d",&x1,&y2,&x2)) {
        int y1 = 0;
        seg[seglen++] = {x1,y1,y2,1};
        seg[seglen++] = {x2,y1,y2,-1};
        native.push_back(y1), native.push_back(y2);
        ++n;
    }
    sort(all(native));
    native.erase(unique(all(native)), native.end());
    build(1,0, native.size() - 2);
    sort(seg, seg + n * 2);
    int ans = 0;
    int now = 0;
    int cnt = 0;
    rep(i,0,n * 2 - 1) {

        while(seg[i].x == seg[i+1].x && i < n * 2 - 1)
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k), i++;
        modify(1, find(seg[i].y1), find(seg[i].y2)-1, seg[i].k);
        int last = tr[1].len;

        if(last != now) {
            res[++cnt] = {seg[i].x, tr[1].len}; 
            res[++cnt] = {seg[i].x, last};
        }
        now = last;
    }
    rep(i,1,cnt) {
        if(i&1) {
            cout<<res[i].vf;
        } else cout<<res[i].vs;
        cout<<" ";
    }
}

signed main()
{
    #ifdef Multiple_groups_of_examples
    int T; cin>>T;
    while(T--)
    #endif
    solve();
    return 0;
}
void inpfile() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}
2023/8/25 22:11
加载中...