oj.uz

답안 #329499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
329499 2020-11-21T11:17:19 Z mickeyandkaka 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 263 ms 71276 KB 
//{{{
#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

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

# 결과 실행 시간 메모리 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 10 ms 2028 KB Output is correct
5 Correct 13 ms 2412 KB Output is correct
6 Correct 13 ms 2284 KB Output is correct
7 Correct 13 ms 2412 KB Output is correct
8 Correct 88 ms 15852 KB Output is correct
9 Correct 189 ms 27372 KB Output is correct
10 Correct 190 ms 30060 KB Output is correct
11 Correct 199 ms 32512 KB Output is correct
12 Correct 200 ms 33260 KB Output is correct
13 Correct 177 ms 38636 KB Output is correct
14 Correct 177 ms 39020 KB Output is correct
15 Correct 253 ms 69356 KB Output is correct
16 Correct 256 ms 69856 KB Output is correct
17 Correct 181 ms 40172 KB Output is correct
18 Correct 184 ms 40232 KB Output is correct
19 Correct 263 ms 71276 KB Output is correct
20 Correct 259 ms 71276 KB Output is correct