Submission #3965257
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
template<typename T> constexpr function<T(T, int)> ex_multiplies(T initE) {
return [&initE](const T& x, size_t y) -> const T { return (x == initE) ? x : x * y; };
}
template<typename T, typename E> struct LazySegmentTree {
using F = function<T(T, T)>;
using G = function<T(T, E)>;
using H = function<E(E, E)>;
using P = function<E(E, int)>;
int n;
T initT;
E initE;
F f;
G g;
H h;
P p;
vector<T> data;
vector<E> lazy;
LazySegmentTree() {}
LazySegmentTree(int n_, F f, G g, H h, T initT = INT_MAX, E initE = INT_MAX,
vector<T> v = vector<T>(), P p = [](E a, size_t b) { ++b; return a; })
: f(f), g(g), h(h), initT(initT), initE(initE), p(p) {
n = 1;
while (n < n_) n *= 2;
data.assign(n * 2 - 1, initT);
lazy.assign(n * 2 - 1, initE);
if (n_ == v.size()) build(v);
}
void build(vector<T> v) {
for (int i = 0; i < v.size(); ++i) data[i + n - 1] = v[i];
for (int i = n - 2; i >= 0; --i) {
data[i] = f(data[i * 2 + 1], data[i * 2 + 2]);
}
}
inline void eval(int len, int k) {
if (lazy[k] == initE) return;
if (k * 2 + 1 < n * 2 - 1) {
lazy[k * 2 + 1] = h(lazy[k * 2 + 1], lazy[k]);
lazy[k * 2 + 2] = h(lazy[k * 2 + 2], lazy[k]);
}
data[k] = g(data[k], p(lazy[k], len));
lazy[k] = initE;
}
T update(int a, int b, E x, int k = 0, int l = 0, int r = -1) {
if (r < 0) r = n;
eval(r - l, k);
if (b <= l || r <= a) return data[k];
if (a <= l && r <= b) {
lazy[k] = h(lazy[k], x);
return g(data[k], p(lazy[k], r - l));
}
T vl = update(a, b, x, k * 2 + 1, l, (l + r) / 2);
T vr = update(a, b, x, k * 2 + 2, (l + r) / 2, r);
return data[k] = f(vl, vr);
}
T query(int a, int b, int k = 0, int l = 0, int r = -1) {
if (r < 0) r = n;
eval(r - l, k);
if (b <= l || r <= a) return initT;
if (a <= l && r <= b) return data[k];
T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return f(vl, vr);
}
};
//
// e.g.
// | f | g | h | initT | initE | p
// -----+-----------+-------+-------+-----------+-------+--------
// RMQ | min / max | | | INF / 0 | | (mult)
// RSQ | plus | | | 0 | | (mult)
// RUQ | | (ass) | (ass) | | INF | (mult)
// RAQ | | plus | plus | | 0 | (mult)
//
// (ass) := ex_assign;
// (mult) := ex_multiplies;
//
const int initT = 1e9;
const int initE = 0;
const LazySegmentTree<int, int>::F f = [](int a, int b) { return min(a, b); };
const LazySegmentTree<int, int>::G g = plus<int>();
const LazySegmentTree<int, int>::H h = plus<int>();
const LazySegmentTree<int, int>::P p = ex_multiplies<int>(initE);
int main() {
int N, M;
cin >> N >> M;
LazySegmentTree<int, int> seg(N + 1, f, g, h, initT, initE, vector<int>(N + 1, 0), p);
vector<int> s(M), t(M);
for (int i = 0; i < M; i++) {
cin >> s[i] >> t[i], s[i]--, t[i]--;
seg.update(s[i], t[i] + 1, 1);
}
set<int> ans;
for (int i = 0; i < M; i++) {
seg.update(s[i], t[i] + 1, -1);
if (seg.query(s[i], t[i]) > 0) ans.insert(i + 1);
seg.update(s[i], t[i] + 1, 1);
}
cout << ans.size() << endl;
for (auto x : ans) {
cout << x << endl;
}
}
Submission Info
Submission Time |
|
Task |
B - ドキドキデート大作戦高橋君 |
User |
hrbt |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3359 Byte |
Status |
WA |
Exec Time |
539 ms |
Memory |
14552 KB |
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 |
180 ms |
10752 KB |
subtask1_02.txt |
AC |
366 ms |
14552 KB |
subtask1_03.txt |
WA |
253 ms |
7776 KB |
subtask1_04.txt |
WA |
291 ms |
7912 KB |
subtask1_05.txt |
WA |
291 ms |
7912 KB |
subtask1_06.txt |
AC |
1 ms |
256 KB |
subtask1_07.txt |
WA |
1 ms |
256 KB |
subtask1_08.txt |
AC |
1 ms |
256 KB |
subtask1_09.txt |
AC |
1 ms |
256 KB |
subtask2_01.txt |
WA |
165 ms |
10752 KB |
subtask2_02.txt |
WA |
336 ms |
10752 KB |
subtask2_03.txt |
WA |
2 ms |
256 KB |
subtask2_04.txt |
WA |
2 ms |
256 KB |
subtask2_05.txt |
WA |
2 ms |
256 KB |
subtask2_06.txt |
WA |
2 ms |
256 KB |
subtask2_07.txt |
WA |
2 ms |
256 KB |
subtask2_08.txt |
WA |
539 ms |
7776 KB |