Submission #329499

#	Time	Username	Problem	Language	Result	Execution time	Memory
329499		mickeyandkaka	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	263 ms	71276 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
constexpr int NODES = 1.5e7;
// 1.5e7 * 4int ~ 256MB, 6e5 op in 1s
#define lson(x) (node[x].lc)
#define rson(x) (node[x].rc)
struct Node {
    int lc, rc;
    int mset, sum;
} node[NODES];

struct segtree{ // TODO pay special attention to MEM LIMIT!!
    static const int NO_OP = INT_MAX - 1;
    int _n, cnt;
    segtree(int n) : _n(n), cnt(0) { new_node(1, n + 1); };

    inline int new_node(int lx, int rx) {
        ++cnt;
        node[cnt].sum = 0;
        node[cnt].mset = NO_OP;
        return cnt;
    }

    inline void pushup(int x) { // 1
        node[x].sum = node[lson(x)].sum + node[rson(x)].sum;
    }

    inline void push(int x, int lx, int rx, int mid) {
        if (!node[x].lc) node[x].lc = new_node(lx, mid), node[x].rc = new_node(mid, rx);

        int& mset = node[x].mset;
        if (mset != NO_OP) {
            node[lson(x)].sum = (mid - lx) * mset;
            node[lson(x)].mset = mset;

            node[rson(x)].sum = (rx - mid) * mset;
            node[rson(x)].mset = mset;
            mset = NO_OP;
        }
    }

    void set(int x, int lx, int rx, int l, int r, int v) {
        if (r <= lx || rx <= l) return;
        if (l <= lx && rx <= r) {
            node[x].mset = v;
            node[x].sum = (rx - lx) * v;
            return;
        }

        int mid = lx + (rx - lx) / 2;
        push(x, lx, rx, mid);

        if(l < mid) set(lson(x), lx, mid, l, r, v);
        if(r > mid) set(rson(x), mid, rx, l, r, v);
        pushup(x);
    }

    int query(int x, int lx, int rx, int l, int r) {
        if (r <= lx || rx <= l) return 0;
        if (l <= lx && rx <= r) return node[x].sum;

        int mid = lx + (rx - lx) / 2;
        push(x, lx, rx, mid);

        int vl = 0, vr = 0;
        if(l < mid) vl = query(lson(x), lx, mid, l, r);
        if(r > mid) vr = query(rson(x), mid, rx, l, r);
        return vl + vr; // 3
    }
};
// clang-format on

int readint()  // for integer
{
    char c;
    while (c = getchar(), '-' != c && !isdigit(c))
        if (c == EOF) return EOF;
    int f = 1;
    if ('-' == c) f = -1, c = getchar();
    int x = c - '0';
    while (isdigit(c = getchar())) x = x * 10 + c - '0';
    return x * f;
}

void write(int a)  // NOTICE a >= 0
{
    if (a > 9) write(a / 10);
    putchar(a % 10 + '0');
}

int m;
int op, x, y;

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

    while (~scanf("%d", &m))
    {
        int n = 1000000000;
        segtree tree(n);
        int c = 0;

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

                int ans = tree.query(1, 1, n + 1, x + c, y + c);
                printf("%d\n", ans);
                c = ans;
            }
        }
    }

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100