Submission #329337

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
329337	2020-11-20T15:27:24 Z	mickeyandkaka	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	476 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, 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

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.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	20 ms	8044 KB	Output is correct
5	Correct	26 ms	9708 KB	Output is correct
6	Correct	25 ms	9452 KB	Output is correct
7	Correct	25 ms	9708 KB	Output is correct
8	Correct	195 ms	73580 KB	Output is correct
9	Correct	396 ms	127340 KB	Output is correct
10	Correct	403 ms	140652 KB	Output is correct
11	Correct	460 ms	151532 KB	Output is correct
12	Correct	423 ms	155884 KB	Output is correct
13	Correct	396 ms	181612 KB	Output is correct
14	Correct	394 ms	183404 KB	Output is correct
15	Runtime error	476 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-