Submission #329337

#	Time	Username	Problem	Language	Result	Execution time	Memory
329337		mickeyandkaka	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	476 ms	262148 KiB

apple

//{{{
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// clang-format off
void _print() { cerr << "]\033[0m\n"; }
template <typename T> void __print(T x) { cerr << x; }
template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#ifdef LOCAL
#define debug(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m["; _print(x)
#define debug_arr(x...) cerr << "\033[1;34m[" << #x << "] = \033[1;32m" << (x) << "\033[0m\n"
#else
#define debug(x...)
#define debug_arr(x...)
#endif
// clang-format on
//}}}

// clang-format off
struct SegNode {
    static const LL NO_OP = LLONG_MAX - 1;
    LL lo, hi;
    SegNode *l = 0, *r = 0;
    // TODO 0 maintain init element
    LL mset = NO_OP, madd = 0;
    LL val = 0, sum = 0;
    SegNode(int lo, int hi) : lo(lo), hi(hi) {}

    void pushup() { // TODO 1
        val = max(l->val, r->val);
        sum = l->sum + r->sum;
    }

    SegNode(vi& v, int lo, int hi) : lo(lo), hi(hi) {
        if (lo + 1 == hi) {
            val = sum = v[lo]; // TODO 2
            return;
        }

        int mid = lo + (hi - lo) / 2;
        l = new SegNode(v, lo, mid), r = new SegNode(v, mid, hi);
        pushup();
    }

    void push() {
        if (!l) {
            int mid = lo + (hi - lo) / 2;
            l = new SegNode(lo, mid), r = new SegNode(mid, hi);
        }
        if (mset != NO_OP) l->set(lo, hi, mset), r->set(lo, hi, mset), mset = NO_OP;
        else if (madd) l->add(lo, hi, madd), r->add(lo, hi, madd), madd = 0;
    }

    pair<LL, LL> query(int L, int R) {
        if (R <= lo || hi <= L) return {LLONG_MIN, 0};
        if (L <= lo && hi <= R) return {val, sum};
        push();
        auto vl = l->query(L, R), vr = r->query(L, R);
        return {max(vl.first, vr.first), vl.second + vr.second}; // TODO 3
    }

    void set(int L, int R, LL x) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R) {
            mset = val = x, madd = 0;
            sum = 1ll * (hi - lo) * x;
            return;
        }

        push(), l->set(L, R, x), r->set(L, R, x);
        pushup();
    }
    void add(int L, int R, LL x) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R) {
            if (mset != NO_OP) mset += x;
            else madd += x;

            val += x;
            sum += 1ll * (hi - lo) * x;
            return;
        }
        push(), l->add(L, R, x), r->add(L, R, x);
        pushup();
    }
};
// clang-format on

int n, m;
int op, x, y;

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

    while (~scanf("%d", &m))
    {
        SegNode* tree = new SegNode(1, 1000000000 + 1);
        int c = 0;

        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &op, &x, &y);
            if (op == 2)
            {
                y++;
                tree->set(x + c, y + c, 1);
            }
            else
            {
                y++;

                LL ans = tree->query(x + c, y + c).second;
                printf("%lld\n", ans);
                c = ans;
            }
        }
    }

    return 0;
}

Compilation message (stderr)

apple.cpp: In function 'int main()':
apple.cpp:114:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |             scanf("%d%d%d", &op, &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100