Submission #329344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
329344	2020-11-20T15:37:56 Z	mickeyandkaka	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	519 ms	207940 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	17 ms	4844 KB	Output is correct
5	Correct	20 ms	5868 KB	Output is correct
6	Correct	23 ms	5740 KB	Output is correct
7	Correct	20 ms	5868 KB	Output is correct
8	Correct	156 ms	43716 KB	Output is correct
9	Correct	321 ms	75628 KB	Output is correct
10	Correct	328 ms	83564 KB	Output is correct
11	Correct	355 ms	90124 KB	Output is correct
12	Correct	352 ms	92652 KB	Output is correct
13	Correct	316 ms	108140 KB	Output is correct
14	Correct	321 ms	109036 KB	Output is correct
15	Correct	500 ms	201964 KB	Output is correct
16	Correct	499 ms	203500 KB	Output is correct
17	Correct	318 ms	114796 KB	Output is correct
18	Correct	319 ms	114920 KB	Output is correct
19	Correct	511 ms	207852 KB	Output is correct
20	Correct	519 ms	207940 KB	Output is correct