답안 #956075

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956075 2024-04-01T02:00:59 Z Rifal 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
251 ms 201948 KB
#include <bits/stdc++.h>
#include <fstream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define mod 1000000007
#define INF 1000000001
#define INF2 2000000000
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
const int P = 1007;
typedef long long ll;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int N = 1e5 + 5;
struct Node {
    ll sum = 0, numl = 0, numr = 0;
    bool lazy = false;
};
Node seg[N*64];
int cnt = 2;
void push(int x, ll l, ll r) {
    if(l == r || seg[x].lazy == false) return;
    ll mid = (l+r)/2ll;
    if(seg[x].numl == 0) {
        seg[x].numl = cnt; cnt++; }
    if(seg[x].numr == 0) {
        seg[x].numr = cnt; cnt++; }
    seg[x].lazy = false;
    int indxl = seg[x].numl, indxr = seg[x].numr;
    seg[indxl].lazy = true;
    seg[indxr].lazy = true;
    seg[indxl].sum = (mid-l+1ll);
    seg[indxr].sum = (r-(mid+1ll)+1ll);
}
void Update(int x, ll l, ll r, ll L, ll R) {
    push(x,l,r);
    if(l > R || r < L) {
        return;
    }
    else if(l >= L && r <= R) {
        seg[x].lazy = true;
        seg[x].sum = (r-l+1ll);
    }
    else {
        ll mid = (l+r)/2ll;
        if(seg[x].numl == 0) {
                seg[x].numl = cnt; cnt++;
        }
        if(seg[x].numr == 0) {
            seg[x].numr = cnt; cnt++;
        }
        int indxl = seg[x].numl, indxr = seg[x].numr;
        if(L > mid) {
            Update(indxr,mid+1ll,r,L,R);
        }
        else if(R <= mid) {
            Update(indxl,l,mid,L,R);
        }
        else {
            Update(indxl,l,mid,L,R); Update(indxr,mid+1ll,r,L,R);
        }
        seg[x].sum = seg[indxl].sum+seg[indxr].sum;
    }
}
ll sol(int x, ll l, ll r, ll L, ll R) {
    push(x,l,r);
    if(l > R || r < L) {
        return 0;
    }
    else if(l >= L && r <= R) {
        return seg[x].sum;
    }
    else {
        ll mid = (l+r)/2ll;
        if(seg[x].numl == 0) {
            seg[x].numl = cnt; cnt++;
        }
        if(seg[x].numr == 0) {
            seg[x].numr = cnt; cnt++;
        }
        int indxl = seg[x].numl, indxr = seg[x].numr;
        if(L > mid) {
            return sol(indxr,mid+1ll,r,L,R);
        }
        else if(R <= mid) {
            return sol(indxl,l,mid,L,R);
        }
        else {
        return sol(indxl,l,mid,L,R)+sol(indxr,mid+1ll,r,L,R);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int m; cin >> m; ll c = 0;
    while(m--) {
        ll d, l, r; cin >> d >> l >> r;
        if(d == 1) {
            ll val = sol(1,1,INF,l+c,r+c);
            cout << val << endl; c = val;
        }
        else {
            Update(1,1,INF,l+c,r+c);
        }
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 12 ms 6748 KB Output is correct
5 Correct 9 ms 6748 KB Output is correct
6 Correct 11 ms 6748 KB Output is correct
7 Correct 10 ms 6748 KB Output is correct
8 Correct 93 ms 41800 KB Output is correct
9 Correct 178 ms 70736 KB Output is correct
10 Correct 188 ms 78916 KB Output is correct
11 Correct 189 ms 85076 KB Output is correct
12 Correct 180 ms 89012 KB Output is correct
13 Correct 155 ms 105556 KB Output is correct
14 Correct 153 ms 107604 KB Output is correct
15 Correct 245 ms 195920 KB Output is correct
16 Correct 239 ms 197716 KB Output is correct
17 Correct 151 ms 113972 KB Output is correct
18 Correct 149 ms 113780 KB Output is correct
19 Correct 244 ms 201808 KB Output is correct
20 Correct 251 ms 201948 KB Output is correct