oj.uz

답안 #919845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919845 2024-02-01T17:46:32 Z Nelt 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 234 ms 170320 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 * 60], R[N * 60], st[N * 60], lazy[N * 60], 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 < 60 * 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";
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 97624 KB Output is correct
2 Correct 16 ms 97628 KB Output is correct
3 Correct 16 ms 97628 KB Output is correct
4 Correct 22 ms 101976 KB Output is correct
5 Correct 24 ms 101976 KB Output is correct
6 Correct 23 ms 101976 KB Output is correct
7 Correct 24 ms 101980 KB Output is correct
8 Correct 81 ms 114512 KB Output is correct
9 Correct 171 ms 122896 KB Output is correct
10 Correct 168 ms 127056 KB Output is correct
11 Correct 194 ms 131084 KB Output is correct
12 Correct 175 ms 131244 KB Output is correct
13 Correct 154 ms 135760 KB Output is correct
14 Correct 148 ms 135244 KB Output is correct
15 Correct 233 ms 166252 KB Output is correct
16 Correct 230 ms 170320 KB Output is correct
17 Correct 146 ms 139600 KB Output is correct
18 Correct 146 ms 139344 KB Output is correct
19 Correct 234 ms 170248 KB Output is correct
20 Correct 232 ms 170316 KB Output is correct