蒟蒻求助!
查看原帖
蒟蒻求助!
486001
Knighthood楼主2022/11/26 08:48

这为什么一直20分啊?

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
#define middle(a, b) ((a + b) >> 1)

const int N = 1e5 + 5;

int p[N << 1], K, x[N], y[N], ans;

class Node{
public:
    int lc, rc, sum, lazy;
    Node(){
        lc = rc = sum = lazy = 0;
    }
};

class Segment_tree{
#define lc(k) t[k].lc
#define rc(k) t[k].rc
#define s(k) t[k].sum
#define z(k) t[k].lazy
private:
    int tot = 0;
    vector<Node> t;
    void up(int k, int L, int R){
        s(k) = (z(k) >= K ? p[R] - p[L] : s(lc(k)) + s(rc(k)));
    }
    void down(int k, int L, int R){
        int mid = middle(L, R);
        z(lc(k)) += z(k);
        z(rc(k)) += z(k);
        up(lc(k), L, mid);
        up(rc(k), mid, R);
    }
public:
    explicit Segment_tree(int n){
        t.resize(2 * n + 114);
    }

    void Modify(int &k, int l, int r, int L, int R){
        if(!k)
            k = ++tot;
        if(l <= p[L] && p[R] <= r){
            ++z(k);
            up(k, L, R);
            return;
        }
        if(L + 1 == R)
            return;
        int mid = middle(L, R);
        down(k, L, R);
        if(l <= p[mid])
            Modify(lc(k), l, r, L, mid);
        if(r > p[mid])
            Modify(rc(k), l, r, mid, R);
        up(k, L, R);
    }

    int Ask(int root){return s(root);}
};

int main(){
// #define LOCAL
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n >> K;
    int tmp = 0, tot = 0;
    for(int i = 1; i <= n; ++i){
        int OMG;
        char op;
        cin >> OMG >> op;
        if(op == 'L'){
            y[i] = tmp;
            tmp += OMG;
            x[i] = tmp;
        }
        else{
            x[i] = tmp;
            tmp -= OMG;
            y[i] = tmp;
        }
        p[++tot] = x[i];
        p[++tot] = y[i];
    }

    sort(p + 1, p + 1 + tot);
    int kcx = (int)(unique(p + 1, p + 1 + tot) - p - 1);
    Segment_tree tree(kcx);
    int root = 0;

    for(int i = 1; i <= n; ++i){
//        cerr << y[i] << ' ' << x[i] << '\n';
        tree.Modify(root, y[i], x[i], 1, kcx);
    }

    cout << tree.Ask(root) << '\n';

    return 0;
}
2022/11/26 08:48
加载中...