답안 #474642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
474642 2021-09-19T08:34:07 Z Marslai24 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
288 ms 262148 KB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()

const int INF = 1e18, MOD = 1e9 + 7, N = 1e7 + 1;

void setIO(string name = ""){
    ios::sync_with_stdio(false);
    cin.tie(0);
}

template<class T> struct seg{
    T val, lz;
    seg<T> *lc, *rc;
    int sz;
    seg(int n) : sz(n){val = lz = 0; lc = rc = NULL;}
    void pull(){
        val = (lc ? lc -> val : 0) + (rc ? rc -> val : 0);
    }
    void push(int l, int r){
        int m = l + r >> 1;
        if(!lc)lc = new seg(m - l);
        if(!rc)rc = new seg(r - m);
        if(!lz)return;
        lc -> val = lc -> sz;
        lc -> lz = 1;
        rc -> val = rc -> sz;
        rc -> lz = 1;
        lz = 0;
    }
    void add(int a, int b, T v, int l, int r){
        if(a <= l && b >= r){
            val = r - l, lz = 1;
            return;
        }
        push(l, r);
        int m = l + r >> 1;
        if(a < m){
            lc -> add(a, b, v, l, m);
        }
        if(b > m){
            rc -> add(a, b, v, m, r);
        }
        pull();
    }
    T query(int a, int b, int l, int r){
        if(a <= l && b >= r)return val;
        push(l, r);
        int m = l + r >> 1, ans = 0;
        if(a < m)ans += lc -> query(a, b, l, m);
        if(b > m)ans += rc -> query(a, b, m, r);
        return ans;
    }
    void add(int a, int b, T v){add(a, b, v, 0, sz);}
    T query(int a, int b){return query(a, b, 0, sz);}
};

signed main(){
    setIO();
    seg<int> rt(N);
    int n, c = 0;
    cin >> n;
    while(n--){
        int t, l, r;
        cin >> t >> l >> r;
        l = l - 1 + c, r = r + c;
        if(t == 1){
            c = rt.query(l, r);
            cout << c << '\n';
        }else{
            rt.add(l, r, 1);
        }
    }
}

Compilation message

apple.cpp: In instantiation of 'T seg<T>::query(long long int, long long int, long long int, long long int) [with T = long long int]':
apple.cpp:56:39:   required from 'T seg<T>::query(long long int, long long int) [with T = long long int]'
apple.cpp:69:30:   required from here
apple.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int m = l + r >> 1, ans = 0;
      |                 ~~^~~
apple.cpp: In instantiation of 'void seg<T>::add(long long int, long long int, T, long long int, long long int) [with T = long long int]':
apple.cpp:55:36:   required from 'void seg<T>::add(long long int, long long int, T) [with T = long long int]'
apple.cpp:72:27:   required from here
apple.cpp:38:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int m = l + r >> 1;
      |                 ~~^~~
apple.cpp: In instantiation of 'void seg<T>::push(long long int, long long int) [with T = long long int]':
apple.cpp:49:9:   required from 'T seg<T>::query(long long int, long long int, long long int, long long int) [with T = long long int]'
apple.cpp:56:39:   required from 'T seg<T>::query(long long int, long long int) [with T = long long int]'
apple.cpp:69:30:   required from here
apple.cpp:22:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int m = l + r >> 1;
      |                 ~~^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 13 ms 4928 KB Output is correct
5 Correct 17 ms 5988 KB Output is correct
6 Correct 21 ms 5836 KB Output is correct
7 Correct 20 ms 6000 KB Output is correct
8 Correct 131 ms 44808 KB Output is correct
9 Correct 267 ms 76976 KB Output is correct
10 Correct 276 ms 85064 KB Output is correct
11 Correct 285 ms 91320 KB Output is correct
12 Correct 288 ms 94228 KB Output is correct
13 Runtime error 242 ms 262148 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -