Submission #1501740
Source Code Expand
#include <bits/stdc++.h>
#define rep(n) for (int I = 0; (I) < (n); ++(I) )
#define repeat(i, n) for( int i = 0; (i) < (n); ++(i) )
#define repeat_to(i, n) for( int i = 0; (i) <= (n); ++(i) )
#define repeat_from(i, m, n) for( int i = (m); (i) < (n); ++(i) )
#define repeat_from_to(i, m, n) for( int i = (m); (i) <= (n); ++(i) )
#define repeat_from_reverse(i, m, n) for( int i = (n) - 1; (i) >= (m); --(i) )
#define dump(x) cout << " " << #x << "=" << x
#define vdump(v) for(size_t t=0; t<v.size(); ++t){cout << " " << #v << "[" << t << "]=" << v[t];} cout << endl
using namespace std;
using lint = long long;
using ld = long double;
// セグメントツリー (点変更・区間クエリ)
template <typename monoid>
struct segment_tree {
using M = monoid;
using T = typename M::value_type;
size_t sz;
vector<T> x;
segment_tree(size_t n = 0) {
sz = 1;
while (sz < n) sz *= 2;
x.assign(sz * 2, M::id());
initialize();
}
template <typename iterator>
segment_tree(iterator first, iterator last) {
sz = 1;
size_t n = distance(first, last);
while (sz < n) sz *= 2;
x.assign(sz * 2, M::id());
copy(first, last, x.begin() + sz);
initialize();
}
void fill(const T& val) {
std::fill(x.begin() + sz, x.end(), val);
initialize();
}
void initialize() {
for (int i = (int)sz - 1; i >= 1; --i) {
x[i] = M::op(x[i * 2 + 0], x[i * 2 + 1]);
}
}
T accumulate(size_t l, size_t r) const {
T al = M::id(), ar = M::id();
for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
if (l & 1) al = M::op(al, x[l++]);
if (r & 1) ar = M::op(x[--r], ar);
}
return M::op(al, ar);
}
void update(size_t i, const T &val) {
x[i += sz] = val;
while (i > 1) {
x[i / 2] = M::op(x[i], x[i ^ 1]);
i /= 2;
}
}
T operator[](size_t i) const { return x[sz + i]; }
};
template <typename T>
struct min_monoid {
using value_type = T;
static constexpr T id() { return numeric_limits<T>::max(); }
static T op(const T &a, const T &b) { return min(a, b); }
};
template <typename T>
struct max_monoid {
using value_type = T;
static constexpr value_type id() { return numeric_limits<value_type>::min(); }
static value_type op(const value_type &a, const value_type &b) { return max(a, b); }
};
template <typename T>
struct sum_monoid {
using value_type = T;
static constexpr value_type id() { return 0; }
static value_type op(const value_type &a, const value_type &b) { return a + b; }
};
template <typename value_type>
using rmq = segment_tree<min_monoid<value_type>>;
template <typename value_type>
using rsq = segment_tree<sum_monoid<value_type>>;
int main(void) {
int n, m; cin >> n >> m;
vector<int> a(n+1, 0);
vector<int> p(m, 0);
vector<int> q(m, 0);
repeat(i, m) {
int x, y; cin >> x >> y;
p[i] = x;
q[i] = y;
++a[x];
--a[y+1];
}
vector<int> b(n+1, 0);
b[0] = a[0];
repeat_from(i, 1, n) {
b[i] = b[i-1] + a[i];
}
//vdump(a);
//vdump(b);
rmq<int> sg(b.begin(), b.end());
vector<int> ans;
repeat(i, m) {
int minval = sg.accumulate(p[i], q[i]);
if (minval != 1)
ans.push_back(i+1);
}
int N = ans.size();
cout << N << endl;
repeat(i, N) cout << ans[i] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - ドキドキデート大作戦高橋君 |
User |
maphylageo |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3688 Byte |
Status |
WA |
Exec Time |
228 ms |
Memory |
8568 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 |
65 ms |
7424 KB |
subtask1_02.txt |
AC |
218 ms |
8568 KB |
subtask1_03.txt |
WA |
140 ms |
5244 KB |
subtask1_04.txt |
WA |
148 ms |
4860 KB |
subtask1_05.txt |
WA |
151 ms |
4860 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 |
AC |
209 ms |
8568 KB |
subtask2_02.txt |
AC |
225 ms |
8568 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 |
WA |
1 ms |
256 KB |
subtask2_07.txt |
WA |
1 ms |
256 KB |
subtask2_08.txt |
AC |
228 ms |
5752 KB |