Submission #684076

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684076	2023-01-20T10:02:20 Z	noedit	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	510 ms	262144 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	24 ms	8556 KB	Output is correct
5	Correct	28 ms	10360 KB	Output is correct
6	Correct	28 ms	9952 KB	Output is correct
7	Correct	26 ms	10320 KB	Output is correct
8	Correct	211 ms	77064 KB	Output is correct
9	Correct	414 ms	130904 KB	Output is correct
10	Correct	510 ms	146868 KB	Output is correct
11	Correct	434 ms	159452 KB	Output is correct
12	Correct	505 ms	164912 KB	Output is correct
13	Correct	416 ms	204976 KB	Output is correct
14	Correct	429 ms	207020 KB	Output is correct
15	Runtime error	461 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-