Submission #329341

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
329341	2020-11-20T15:30:40 Z	mickeyandkaka	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	594 ms	262148 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 LL NO_OP = LLONG_MAX - 1;
    LL lo, hi;
    SegNode *l = 0, *r = 0;
    // TODO 0 maintain init element
    LL mset = NO_OP;
    LL sum = 0;
    SegNode(int lo, int hi) : lo(lo), hi(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;
    }

    LL 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, LL x) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R) {
            mset = x;
            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);
                printf("%lld\n", ans);
                c = ans;
            }
        }
    }

    return 0;
}

Compilation message

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

Subtask #1

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	22 ms	6380 KB	Output is correct
5	Correct	23 ms	7768 KB	Output is correct
6	Correct	24 ms	7404 KB	Output is correct
7	Correct	23 ms	7660 KB	Output is correct
8	Correct	179 ms	58112 KB	Output is correct
9	Correct	357 ms	100716 KB	Output is correct
10	Correct	389 ms	111212 KB	Output is correct
11	Correct	383 ms	119788 KB	Output is correct
12	Correct	396 ms	123372 KB	Output is correct
13	Correct	364 ms	143724 KB	Output is correct
14	Correct	364 ms	145132 KB	Output is correct
15	Runtime error	594 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-