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
AC × 3
AC × 8
WA × 4
AC × 8
WA × 12
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