oj.uz

답안 #530821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530821 2022-02-26T21:47:34 Z Evang 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 627 ms 256712 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb(x) push_back(x)
#define eb(args...) emplace_back(args)
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 1<<30;
int q;
struct node {
    node *left = nullptr, *right = nullptr;
    int sum;
    bool set;
    node *l(){
        if(left==nullptr)
            left = new node;
        return left;
    }
    node *r(){
        if(right==nullptr)
            right = new node;
        return right;
    }
};

void push(node *v, int il, int ir){
    if(!v->set)
        return;
    if(il!=ir)
        v->l()->set = v->r()->set = 1;
    v->sum = ir-il+1;
    v->set = 0;
}

void pull(node *v){
    v->sum = v->r()->sum + v->l()->sum;
}

void upd(int l, int r, node *v, int il, int ir){
    push(v, il, ir);
    if(ir < l || r < il)
        return;
    if(l <= il && ir <= r){
        v->set = 1;
        push(v, il, ir);
        return;
    }

    int im = (il+ir)/2;
    upd(l, r, v->l(), il, im);
    upd(l, r, v->r(), im+1, ir);
    pull(v);
}

int qry(int l, int r, node *v, int il, int ir){
    push(v, il, ir);
    if(ir < l || r < il)
        return 0;
    if(l <= il && ir <= r)
        return v->sum;

    int im = (il+ir)/2;
    return qry(l, r, v->l(), il, im) + qry(l, r, v->r(), im+1, ir);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> q;
    node *root = new node;
    int c = 0;
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        l += c;
        r += c;
        if(t==1)
            cout << (c = qry(l, r, root, 1, N)) << el;
        else
            upd(l, r, root, 1, N);
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 17 ms 5696 KB Output is correct
5 Correct 20 ms 6912 KB Output is correct
6 Correct 17 ms 6696 KB Output is correct
7 Correct 18 ms 6864 KB Output is correct
8 Correct 165 ms 50320 KB Output is correct
9 Correct 347 ms 89232 KB Output is correct
10 Correct 373 ms 96168 KB Output is correct
11 Correct 367 ms 104388 KB Output is correct
12 Correct 387 ms 107780 KB Output is correct
13 Correct 327 ms 136064 KB Output is correct
14 Correct 321 ms 137500 KB Output is correct
15 Correct 595 ms 248676 KB Output is correct
16 Correct 545 ms 250692 KB Output is correct
17 Correct 316 ms 142396 KB Output is correct
18 Correct 343 ms 142400 KB Output is correct
19 Correct 627 ms 256544 KB Output is correct
20 Correct 521 ms 256712 KB Output is correct