Submission #1245672
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];
int main() {
int n, m, i;
vector <int> v;
scanf("%d %d", &n, &m);
segment_tree_lazy <long long> s(n, [](long long x, long long y, int len) { return x == 1e18 ? y : 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
Submission Time
2017-04-27 02:38:09+0900
Task
B - ドキドキデート大作戦高橋君
User
kawatea
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
4910 Byte
Status
WA
Exec Time
154 ms
Memory
13560 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:134: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:118: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:123: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
Set Name
Sample
Subtask1
All
Score / Max Score
0 / 0
0 / 30
0 / 70
Status
Set Name
Test Cases
Sample
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt
Case Name
Status
Exec Time
Memory
subtask0_sample_01.txt
AC
1 ms
256 KB
subtask0_sample_02.txt
AC
1 ms
256 KB
subtask0_sample_03.txt
AC
1 ms
256 KB
subtask1_01.txt
AC
41 ms
12416 KB
subtask1_02.txt
AC
53 ms
13432 KB
subtask1_03.txt
WA
42 ms
6780 KB
subtask1_04.txt
WA
47 ms
6652 KB
subtask1_05.txt
WA
48 ms
6652 KB
subtask1_06.txt
AC
1 ms
256 KB
subtask1_07.txt
AC
1 ms
256 KB
subtask1_08.txt
AC
1 ms
256 KB
subtask1_09.txt
AC
1 ms
256 KB
subtask2_01.txt
AC
92 ms
12920 KB
subtask2_02.txt
AC
81 ms
13560 KB
subtask2_03.txt
WA
1 ms
256 KB
subtask2_04.txt
WA
1 ms
256 KB
subtask2_05.txt
WA
1 ms
256 KB
subtask2_06.txt
AC
1 ms
256 KB
subtask2_07.txt
WA
1 ms
256 KB
subtask2_08.txt
AC
154 ms
8056 KB