Submission #1188276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188276		RedGrey1993	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	502 ms	327680 KiB

apple

#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

// 函数名后面加 ll 就可以计算 long long类型对应的结果
// __builtin_ffs(x)  // 返回x中最后一个为1的位是从后向前的第几位
// __builtin_popcount(x)  // x中1的个数
// __builtin_ctz(x)  // x末尾0的个数。x=0时结果未定义。
// __builtin_clz(x)  // x前导0的个数。x=0时结果未定义。
// __builtin_parity(x)  // x中1的奇偶性。
#define highest_bit1_index(x) (31 - __builtin_clz(x))
#define highest_bit1_index_ll(x) (63 - __builtin_clzll(x))
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif

// 动态分配内存的版本
template <typename T>
struct Node {
    struct _LazyTag {
        static constexpr T NOT_SET = numeric_limits<T>::lowest();
        T additional_val_every_item = 0;
        T set_val_every_item = NOT_SET;
        void Reset() {
            additional_val_every_item = 0;
            set_val_every_item = NOT_SET;
        }
    };
    Node() : sum(0), min(numeric_limits<T>::max()), max(numeric_limits<T>::min()) {}
    Node(const T& v) : sum(v), min(v), max(v) {}
    T sum = 0, min = 0, max = 0;
    T max_prefix = 0;
    _LazyTag lazy_tag;
    int chl = -1, chr = -1;
};
template <typename T>
using LazyTag = typename Node<T>::_LazyTag;

// 动态分配内存的版本，一般是因为数据的范围特别大，无法在一开始就初始化，且查询的时候不会查询到所有的数据范围
// 例如数据范围是0-10^9，但是查询的时候只会查询0-10^6次
template<typename T>
class SegmentTree4 {
public:
    SegmentTree4(unsigned int size) {
        this->size = size;
        data.emplace_back(Node<T>(0));
    }
    // 动态分配内存，无法在一开始就初始化
    // void Init() { Init(0, 0, size); }
    // 将[a,b)范围内所有的值，作对应的更新操作
    void Update(int a, int b, const LazyTag<T>& tag) { Update(a, b, tag, 0, 0, size); }
    // 查询[a,b)范围的目标值
    Node<T> Query(int a, int b) { return Query(a, b, 0, 0, size); }
    // 查询[a,b)范围内，前缀和大于h的第一个位置
    int Query2(int a, int b, int h) { return Query2(a, b, 0, h, 0, size); }

private:
    int GetNode(int k) {
        if (k == -1) {
            data.emplace_back(Node<T>(0));
            k = data.size() - 1;
            // dbg(k)
        }
        return k;
    }
    // 根据不同的情况实现Apply和Combine
    void Apply(const LazyTag<T>& tag, int k, int l, int r) {
        // cerr << "Apply: (l,r) = (" << l << "," << r << ") tag.set_val_every_item = " << tag.set_val_every_item << endl;
        if (tag.set_val_every_item != LazyTag<T>::NOT_SET) {
            data[k].lazy_tag.additional_val_every_item = 0;
            data[k].lazy_tag.set_val_every_item = tag.set_val_every_item;
            data[k].sum = (r - l) * tag.set_val_every_item;
            data[k].max = data[k].min = tag.set_val_every_item;
            data[k].max_prefix = max(T(0), data[k].sum);
        }
        // cerr << "Apply: (l,r) = (" << l << "," << r << ") (k, data[k].sum) = (" << k << "," << data[k].sum << ")" << endl;
        if (tag.additional_val_every_item != 0) {
            data[k].lazy_tag.additional_val_every_item += tag.additional_val_every_item;
            data[k].sum += (r - l) * tag.additional_val_every_item;
            data[k].max += tag.additional_val_every_item;
            data[k].min += tag.additional_val_every_item;
        }
    }

    void Combine(const Node<T>& a, const Node<T>& b, Node<T>& c) {
        c.sum = a.sum + b.sum;
        c.min = min(a.min, b.min);
        c.max = max(a.max, b.max);
        c.max_prefix = max(a.max_prefix, a.sum + b.max_prefix);
    }

    void Update(int a, int b, const LazyTag<T>& tag, int k, int l, int r) {
        if (b <= l || a >= r)  //没有交集
            return;
        else if (a <= l && r <= b) {  //完全包含
            Apply(tag, k, l, r);
        } else {  //有交集
            int mid = l + (r - l) / 2;

            int chl = data[k].chl = GetNode(data[k].chl);
            int chr = data[k].chr = GetNode(data[k].chr);
            // cerr << "Update k: " << k << " data[k].chl: " << data[k].chl << " data[k].chr: " << data[k].chr << endl;
            PushDown(k, chl, chr, l, r);

            Update(a, b, tag, chl, l, mid);
            Update(a, b, tag, chr, mid, r);
            
            Combine(data[chl], data[chr], data[k]);
        }
    }

    inline void PushDown(int k, int chl, int chr, int l, int r) {
        if (r - l > 1) {
            int mid = l + (r - l) / 2;
            Apply(data[k].lazy_tag, chl, l, mid);
            Apply(data[k].lazy_tag, chr, mid, r);
            data[k].lazy_tag.Reset();
        }
    }

    Node<T> Query(int a, int b, int k, int l, int r) {
        // [a,b) 和 [l,r)完全不相交
        if (r <= a || b <= l) {
            return Node<T>();
        }
        // [a,b)完全包含[l,r)，返回当前值
        if (a <= l && r <= b) {
            return data[k];
        }

        int mid = l + (r - l) / 2;
        int chl = data[k].chl = GetNode(data[k].chl);
        int chr = data[k].chr = GetNode(data[k].chr);

        PushDown(k, chl, chr, l, r);
        Node<T> c;
        Combine(Query(a, b, chl, l, mid), Query(a, b, chr, mid, r), c);

        return c;
    }

    int Query2(int a, int b, int k, int& h, int l, int r) {
        // cerr << "a: " << a << " b: " << b << " k: " << k << " h: " << h << " l: " << l << " r: " << r << " data[k].sum: " << data[k].sum << " data[k].max_prefix: " << data[k].max_prefix << endl;
        if (r <= a || b <= l) {
            return -1;
        }

        if (r - l == 1) {
            return h >= data[k].max_prefix ? r : l;
        }

        int mid = l + (r - l) / 2;
        int chl = data[k].chl = GetNode(data[k].chl);
        int chr = data[k].chr = GetNode(data[k].chr);
        // cerr << "Query2 k: " << k << " data[k].chl: " << data[k].chl << " data[k].chr: " << data[k].chr << endl;

        PushDown(k, chl, chr, l, r);
        if (data[chl].max_prefix > h) {
            return Query2(a, b, chl, h, l, mid);
        } else {
            h -= data[chl].sum;
            return Query2(a, b, chr, h, mid, r);
        }
    }

    vector<Node<T>> data;
    int size;
};

class Solution {
public:
    void Solve() {
        const int maxn = 1e9 + 5;
        int m;
        while(cin>>m) {
            int c = 0;
            int op,x,y;
            SegmentTree4<ll> st(maxn);
            rep(i,0,m) {
                cin>>op>>x>>y;
                if (op == 2) {
                    LazyTag<ll> tag;
                    tag.set_val_every_item = 1;
                    st.Update(c+x-1, c+y, tag);
                } else {
                    auto ret = st.Query(c+x-1, c+y);
                    c = ret.sum;
                    cout << c << endl;
                }
            }
        }
        cout.flush();
    }
private:
};

// # define FILE_IO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
    set_io("tmp");
    Solution().Solve();

    return 0;
}

• Subtask 1: 0 / 100