oj.uz

답안 #1096475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096475 2024-10-04T14:50:23 Z Bahamin 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 443 ms 233100 KB 
#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

# 결과 실행 시간 메모리 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