답안 #919843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919843 2024-02-01T17:44:43 Z vjudge1 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
229 ms 192848 KB
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define ss(a) set<a>
#define pp(a, b) pair<a, b>
#define mm(a, b) map<a, b>
#define qq(a) queue<a>
#define pq(a) priority_queue<a>
#define ump(a, b) unordered_map<a, b>
#define ANDROID                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define elif else if
#define endl "\n"
#define pb push_back
#define ins insert
#define logi __lg
#define sqrt sqrtl
#define mpr make_pair
using namespace std;
using namespace __cxx11;
using namespace __gnu_pbds;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e5 + 5;
ll L[N * 30], R[N * 30], st[N * 30], lazy[N * 30], ptr = 2;
void push(ll v, ll l, ll r)
{
    if (!lazy[v])
        return;
    lazy[v] = 0;
    ll mid = (l + r) >> 1;
    if (L[v] == -1)
        L[v] = ptr++;
    if (R[v] == -1)
        R[v] = ptr++;
    st[L[v]] = mid - l + 1, lazy[L[v]] = 1;
    st[R[v]] = r - mid, lazy[R[v]] = 1;
}
ll query(ll i, ll j, ll l, ll r, ll v)
{
    if (v == -1)
        return 0;
    if (i <= l and r <= j)
        return st[v];
    ll mid = (l + r) >> 1;
    push(v, l, r);
    if (j <= mid)
        return query(i, j, l, mid, L[v]);
    if (i > mid)
        return query(i, j, mid + 1, r, R[v]);
    return query(i, j, l, mid, L[v]) + query(i, j, mid + 1, r, R[v]);
}
ll modify(ll i, ll j, ll l, ll r, ll v)
{
    if (v == -1)
        v = ptr++;
    if (max(i, l) > min(j, r))
        return v;
    if (i <= l and r <= j)
    {
        st[v] = r - l + 1;
        lazy[v] = 1;
        return v;
    }
    push(v, l, r);
    ll mid = (l + r) >> 1;
    L[v] = modify(i, j, l, mid, L[v]);
    R[v] = modify(i, j, mid + 1, r, R[v]);
    st[v] = st[L[v]] + st[R[v]];
    return v;
}
void solve()
{
    ll q;
    cin >> q;
    for (ll i = 1; i < 30 * N; i++)
        L[i] = R[i] = -1;
    ll c = 0;
    while (q--)
    {
        ll t, l, r;
        cin >> t >> l >> r;
        l += c, r += c;
        if (t == 2)
            modify(l, r, 1, 1e9, 1);
        else
            cout << (c = query(l, r, 1, 1e9, 1)) << endl;
    }
}
/*

*/
int main()
{
    ANDROID
    // precomp();
    ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        // cout << "Case #" << i << ": ",
        solve();
    cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 51032 KB Output is correct
2 Correct 10 ms 51032 KB Output is correct
3 Correct 9 ms 51028 KB Output is correct
4 Correct 16 ms 53336 KB Output is correct
5 Correct 18 ms 53464 KB Output is correct
6 Correct 18 ms 53764 KB Output is correct
7 Correct 17 ms 53340 KB Output is correct
8 Correct 76 ms 66572 KB Output is correct
9 Correct 165 ms 77824 KB Output is correct
10 Correct 169 ms 82000 KB Output is correct
11 Correct 175 ms 84048 KB Output is correct
12 Correct 185 ms 84164 KB Output is correct
13 Correct 139 ms 90704 KB Output is correct
14 Correct 146 ms 90960 KB Output is correct
15 Runtime error 229 ms 192848 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -