제출 #684076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684076		noedit	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	510 ms	262144 KiB

apple

#include <bits/stdc++.h>
//#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;
//
//#define int long long
////#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

const int MAXN = 1e9;

struct node
{
    node *l = nullptr, *r = nullptr;
    int sum = 0;
    bool pushed = true;
    int ch = -1;
    node() {}
    node(int val)
    {
        sum = val;
    }
};

node *root;

void push(node *v, int tl, int tr)
{
    if (!v) return;
    if (!v->pushed)
    {
        if (tl != tr)
        {
            if (!v->l) v->l = new node();
            v->l->ch = v->ch;
            v->l->pushed = false;
            if (!v->r) v->r = new node();
            v->r->ch = v->ch;
            v->r->pushed = false;
        }
        v->sum = (tr - tl + 1) * v->ch;
        v->ch = -1;
        v->pushed = true;
    }
}

int get_sum(node *v)
{
    if (!v) return 0;
    return v->sum;
}

void update(node *v, int tl, int tr, int l, int r, int x)
{
    push(v, tl, tr);
    if (l > r || l < tl || tr < r) return;
    if (tl == l && tr == r)
    {
        v->ch = x;
        v->pushed = false;
        push(v, tl, tr);
    }
    else
    {
        int tm = (tl + tr) >> 1;
        if (!v->l) v->l = new node();
        update(v->l, tl, tm, l, min(r, tm), x);
        if (!v->r) v->r = new node();
        update(v->r, tm + 1, tr, max(l, tm + 1), r, x);
        v->sum = get_sum(v->l) + get_sum(v->r);
    }
}

int get(node *v, int tl, int tr, int l, int r)
{
    push(v, tl, tr);
    if (l > r || l < tl || tr < r) return 0;
    if (tl == l && tr == r)
    {
        return v->sum;
    }
    int tm = (tl + tr) >> 1;
    int ql = (v->l ? get(v->l, tl, tm, l, min(r, tm)) : 0);
    int qr = (v->r ? get(v->r, tm + 1, tr, max(l, tm + 1), r) : 0);
    return ql + qr;
}

void solve()
{
    int m;
    cin >> m;
    root = new node();
    int c = 0;
    while (m--)
    {
        int d, x, y;
        cin >> d >> x >> y;
        x--; y--;
        x += c; y += c;
        if (d == 1)
        {
            int cur = get(root, 0, MAXN - 1, x, y);
            c = cur;
            cout << cur << endl;
        }
        else
        {
            update(root, 0, MAXN - 1, x, y, 1);
        }
//        for (int i = 0; i < 10; i++)
//        {
//            cout << get(root, 0, MAXN - 1, i, i) << ' ';
//        }
//        cout << endl;
    }
}
//
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
    cerr << endl << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
    return 0;
}
//
//
///*
//4 4
//1 2 1 3
//1 1
//1 2
//1 3
//1 4
//*/

• Subtask 1: 0 / 100