답안 #956070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956070 2024-04-01T01:33:07 Z Rifal 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
1770 ms 262144 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)/2;
    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+1);
    seg[indxr].sum = (r-(mid+1)+1);
}
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+1);
    }
    else {
        ll mid = (l+r)/2;
        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;
        Update(indxl,l,mid,L,R); Update(indxr,mid+1,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)/2;
        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;
        return sol(indxl,l,mid,L,R)+sol(indxr,mid+1,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 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 9 ms 6748 KB Output is correct
5 Correct 11 ms 8880 KB Output is correct
6 Correct 11 ms 8872 KB Output is correct
7 Correct 11 ms 8796 KB Output is correct
8 Correct 98 ms 52052 KB Output is correct
9 Correct 200 ms 89380 KB Output is correct
10 Correct 201 ms 99544 KB Output is correct
11 Correct 189 ms 107600 KB Output is correct
12 Correct 197 ms 111660 KB Output is correct
13 Correct 176 ms 137040 KB Output is correct
14 Correct 174 ms 138280 KB Output is correct
15 Runtime error 1770 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -