Submission #1096475

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1096475	2024-10-04T14:50:23 Z	Bahamin	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	443 ms	233100 KB

apple

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

#define ar array
#define ll long long
#define ld long double
#define sze(x) ((ll)x.size())
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
#define mset(a, x) memset(a, x, sizeof(a))
#define lid childs[id].first
#define rid childs[id].second
#define mid ((r + l) >> 1)
typedef priority_queue <ll, vector<ll>, greater<ll> > max_heap;
typedef priority_queue <ll> min_heap;
const ll MAX_N = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const ll LOG = 30;

vector<pair<ll, ll>> childs;
vector<ll> seg;
vector<ll> ops;

void create(ll l, ll r, ll id)
{
    if (childs[id].first || l == r - 1) return;
    childs[id].first = childs.size();
    childs.push_back(make_pair(0, 0));
    seg.push_back(0);
    ops.push_back(-1);
    childs[id].second = childs.size();
    childs.push_back(make_pair(0, 0));
    seg.push_back(0);
    ops.push_back(-1);
}

void move(ll l, ll r, ll id)
{
    create(l, r, id);
    if (l == r - 1 || ops[id] == -1) return;
    seg[lid] = (mid - l) * ops[id];
    seg[rid] = (r - mid) * ops[id];
    ops[lid] = ops[id];
    ops[rid] = ops[id];
    ops[id] = -1;
}

void upd(ll s, ll t, ll x, ll l, ll r, ll id)
{
    move(l, r, id);
    //cout << l << " " << r << " " << x << endl;
    if (s <= l && t >= r)
    {
        ops[id] = x;
        seg[id] = (r - l) * x;
        return;
    }
    if (s < mid) upd(s, t, x, l, mid, lid);
    if (t > mid) upd(s, t, x, mid, r, rid);
    seg[id] = seg[lid] + seg[rid];
}

ll get(ll s, ll t, ll l, ll r, ll id)
{
    move(l, r, id);
    if (s <= l && t >= r) return seg[id];
    if (s >= r || t <= l) return 0;
    return get(s, t, l, mid, lid) + get(s, t, mid, r, rid);
}

void solve() {
    ll m;
    cin >> m;
    ll c = 0;
    childs.push_back({0, 0});
    seg.push_back(0);
    ops.push_back(-1);
    while (m--)
    {
        ll d, x, y;
        cin >> d >> x >> y;
        x += c;
        y += c;
        if (d == 1)
        {
            ll ans = get(x, y + 1, 0, 1e9 + 1, 0);
            cout << ans << "\n";
            c = ans;
            //upd(x, y + 1, 0, 0, 1e9 + 1, 0);
        } else 
        {
            upd(x, y + 1, 1, 0, 1e9 + 1, 0);
        }
    }
}

int main() {
    sui;
    ll tc = 1;
    //cin >> tc;
    for (ll t = 1; t <= tc; t++) {
        solve();
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	13 ms	8092 KB	Output is correct
5	Correct	17 ms	8472 KB	Output is correct
6	Correct	15 ms	8388 KB	Output is correct
7	Correct	16 ms	8608 KB	Output is correct
8	Correct	127 ms	69236 KB	Output is correct
9	Correct	282 ms	122476 KB	Output is correct
10	Correct	298 ms	123180 KB	Output is correct
11	Correct	299 ms	128556 KB	Output is correct
12	Correct	309 ms	131120 KB	Output is correct
13	Correct	267 ms	148128 KB	Output is correct
14	Correct	257 ms	148916 KB	Output is correct
15	Correct	425 ms	225900 KB	Output is correct
16	Correct	429 ms	227588 KB	Output is correct
17	Correct	265 ms	152116 KB	Output is correct
18	Correct	261 ms	152184 KB	Output is correct
19	Correct	430 ms	232960 KB	Output is correct
20	Correct	443 ms	233100 KB	Output is correct