Submission #1245677

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

template <class T>
class segment_tree_lazy {
    public:
    segment_tree_lazy(int n, function<T(const T&, const T&, int)> merge_func, function<T(const T&, const T&)> calc_func, const T& init = T());
    segment_tree_lazy(T* array, int n, function<T(const T&, const T&, int)> merge_func, function<T(const T&, const T&)> calc_func, const T& init = T());
    ~segment_tree_lazy();
    void update(int x, const T& value);
    void update(int x, int y, const T& value); // [x, y)
    T get(int x);
    T get(int x, int y); // [x, y)
    
    private:
    int size;
    int height;
    function<T(const T&, const T&, int)> merge_func;
    function<T(const T&, const T&)> calc_func;
    T init;
    T* data;
    bool* has_delay;
    T* delay;
    inline void apply(int x, const T& value, int len);
    inline void propagate_all(int x, int y);
    inline void propagate(int x, int len);
};

template <class T> segment_tree_lazy<T>::segment_tree_lazy(int n, function<T(const T&, const T&, int)> merge_func, function<T(const T&, const T&)> calc_func, const T& init) : size(1 << (32 - __builtin_clz(n - 1))), height(31 - __builtin_clz(size)), merge_func(merge_func), calc_func(calc_func), init(init) {
    data = (T *)malloc(sizeof(T) * size * 2);
    has_delay = (bool *)malloc(sizeof(bool) * size);
    delay = (T *)malloc(sizeof(T) * size);
    for (int i = 0; i < size * 2; i++) data[i] = init;
    for (int i = 0; i < size; i++) has_delay[i] = false;
}

template <class T> segment_tree_lazy<T>::segment_tree_lazy(T* array, int n, function<T(const T&, const T&, int)> merge_func, function<T(const T&, const T&)> calc_func, const T& init) : segment_tree_lazy(n, merge_func, calc_func, init) {
    for (int i = 0; i < n; i++) data[size + i] = array[i];
    for (int i = size - 1; i > 0; i--) data[i] = calc_func(data[i * 2], data[i * 2 + 1]);
}

template <class T> segment_tree_lazy<T>::~segment_tree_lazy() {
    free(data);
    free(has_delay);
    free(delay);
}

template <class T> void segment_tree_lazy<T>::update(int x, const T& value) {
    x += size;
    propagate_all(x, x);
    apply(x, value, 1);
    while (x >>= 1) data[x] = calc_func(data[x * 2], data[x * 2 + 1]);
}

template <class T> void segment_tree_lazy<T>::update(int x, int y, const T& value) {
    x += size, y += size;
    propagate_all(x, y - 1);
    bool fx = false, fy = false;
    for (int len = 1; x < y; x >>= 1, y >>= 1, len <<= 1) {
        if (fx) data[x - 1] = calc_func(data[(x - 1) * 2], data[(x - 1) * 2 + 1]);
        if (fy) data[y] = calc_func(data[y * 2], data[y * 2 + 1]);
        if (x & 1) apply(x++, value, len), fx = true;
        if (y & 1) apply(--y, value, len), fy = true;
    }
    for (x--; y > 0; x >>= 1, y >>= 1) {
        if (fx) data[x] = calc_func(data[x * 2], data[x * 2 + 1]);
        if (fy && (!fx || x != y)) data[y] = calc_func(data[y * 2], data[y * 2 + 1]);
    }
}

template <class T> T segment_tree_lazy<T>::get(int x) {
    x += size;
    propagate_all(x, x);
    return data[x];
}

template <class T> T segment_tree_lazy<T>::get(int x, int y) {
    T vl = init, vr = init;
    x += size, y += size;
    propagate_all(x, y - 1);
    for (; x < y; x >>= 1, y >>= 1) {
        if (x & 1) vl = calc_func(vl, data[x++]);
        if (y & 1) vr = calc_func(data[--y], vr);
    }
    return calc_func(vl, vr);
}

template <class T> inline void segment_tree_lazy<T>::apply(int x, const T& value, int len) {
    data[x] = merge_func(data[x], value, len);
    if (x < size) {
        if (!has_delay[x]) {
            has_delay[x] = true;
            delay[x] = value;
        } else {
            delay[x] = merge_func(delay[x], value, 1);
        }
    }
}

template <class T> inline void segment_tree_lazy<T>::propagate_all(int x, int y) {
    for (int i = height, len = size >> 1; i > 0; i--, len >>= 1) propagate(x >> i, len), propagate(y >> i, len);
}

template <class T> inline void segment_tree_lazy<T>::propagate(int x, int len) {
    if (!has_delay[x]) return;
    apply(x * 2, delay[x], len);
    apply(x * 2 + 1, delay[x], len);
    has_delay[x] = false;
}

int a[300000][2];
long long b[300000];

int main() {
    int n, m, i;
    vector <int> v;
    
    scanf("%d %d", &n, &m);
    
    segment_tree_lazy <long long> s(b, n, [](long long x, long long y, int len) { return x + y; }, [](long long x, long long y) { return min(x, y); }, 1e18);
    
    for (i = 0; i < m; i++) {
        scanf("%d %d", &a[i][0], &a[i][1]);
        
        a[i][0]--;
        
        s.update(a[i][0], a[i][1], 1);
    }
    
    for (i = 0; i < m; i++) {
        if (s.get(a[i][0], a[i][1]) > 1) v.push_back(i + 1);
    }
    
    printf("%d\n", v.size());
    for (i = 0; i < v.size(); i++) printf("%d\n", v[i]);
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:135:28: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<int>::size_type {aka long unsigned int}’ [-Wformat=]
     printf("%d\n", v.size());
                            ^
./Main.cpp:119:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
                           ^
./Main.cpp:124:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i][0], &a[i][1]);
                                           ^

Judge Result