Submission #329344

#	Time	Username	Problem	Language	Result	Execution time	Memory
329344		mickeyandkaka	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	519 ms	207940 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 int NO_OP = INT_MAX - 1;
    int lo, hi;
    SegNode *l = 0, *r = 0;
    // TODO 0 maintain init element
    int mset = NO_OP;
    int sum = 0;
    SegNode(int lo, int hi) : lo(lo), hi(hi) {
        assert(lo + 1 <= hi);
    }

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

    SegNode(vi& v, int lo, int hi) : lo(lo), hi(hi) {
        if (lo + 1 == hi) {
            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;
    }

    int query(int L, int R) {
        if (R <= lo || hi <= L) return 0;
        if (L <= lo && hi <= R) return sum;
        push();
        auto vl = l->query(L, R), vr = r->query(L, R);
        return vl + vr;
    }

    void set(int L, int R, int x) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R) {
            mset = x;
            sum = (hi - lo);
            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++;

                int ans = tree->query(x + c, y + c);
                printf("%d\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: 100 / 100