| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 882938 |
2023-12-04T08:06:10 Z |
WLZ |
Index (COCI21_index) |
C++17 |
|
3 ms |
5980 KB |
// https://oj.uz/problem/view/COCI21_index
#include <iostream>
#include <vector>
using namespace std;
#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif
#include <cassert>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <string>
namespace fast_input {
constexpr int BUF_SZ = 1 << 18;
char buf[BUF_SZ];
int pos = 0, len = 0;
struct fast_reader { void tie(int *x) { (void) x; } } fcin;
#define rd (pos == len ? (pos = 0, (!(len = (int) fread(buf, 1, BUF_SZ, stdin)) ? EOF : buf[pos++])) : buf[pos++])
template<typename T>
inline void read(T &x) {
short sgn = 1; char c;
while (!std::isdigit(c = rd)) if (c == '-') sgn = -sgn;
x = c - '0';
while (std::isdigit(c = rd)) { x = x * 10 + (c - '0'); }
x *= sgn;
}
template<>
inline void read<std::string>(std::string &s) {
char c;
s = "";
while (!std::isspace(c = rd)) s += c;
}
fast_reader &getline(fast_reader &in, std::string &s) {
s.clear(); char c;
while ((c = rd) != '\n') s += c;
return in;
}
#undef rd
} // namespace fast_input
template<typename T>
fast_input::fast_reader &operator>>(fast_input::fast_reader &in, T &x) { fast_input::read(x); return in; }
namespace fast_output {
constexpr int BUF_SZ = 1 << 18;
char buf[BUF_SZ];
int pos;
struct fast_writer {} fcout;
void flush() { fwrite(buf, 1, pos, stdout); pos = 0; }
void sync_with_stdio(bool b) { (void) b; assert(std::atexit(flush) == 0); }
#define wt(c) ((pos == BUF_SZ ? flush() : (void) 0), buf[pos++] = (c))
template<typename T>
inline void write(const T &y) {
T x = y;
static char num_buf[100];
if (x < 0) wt('-'), x = -x;
int len = 0;
for (; x >= 10; x /= 10) num_buf[len++] = (x % 10) + '0';
wt(x + '0');
while (len) wt(num_buf[--len]);
}
template<>
inline void write(const char &c) { wt(c); }
template<>
inline void write<std::string>(const std::string &s) {
for (const char &c : s) wt(c);
}
#undef wt
} // namespace fast_output
template<typename T>
fast_output::fast_writer &operator<<(fast_output::fast_writer &out, const T &x) { fast_output::write(x); return out; }
#define cin fast_input::fcin
#define ios fast_output
#define cout fast_output::fcout
#define getline fast_input::getline
#include <limits>
// Semigroup, Monoid, Group, AbelianGroup
template<typename _T>
struct addition {
using T = _T;
static constexpr T e = 0;
static constexpr T op(const T &a, const T &b) { return a + b; };
static constexpr T inv(const T &a) { return -a; }
};
// Semigroup, Monoid
template<typename _T>
struct minimum {
using T = _T;
static constexpr T e = std::numeric_limits<T>::max();
static constexpr const T &op(const T &a, const T &b) { return a < b ? a : b; }
};
// Semigroup, Monoid
template<typename _T>
struct maximum {
using T = _T;
static constexpr T e = std::numeric_limits<T>::min();
static constexpr const T &op(const T &a, const T &b) { return a < b ? b : a; }
};
#include <vector>
template<typename _Sg>
class persistent_segment_tree {
using T = typename _Sg::T;
public:
using value_type = T;
persistent_segment_tree() : n(0) {}
template<typename ...Args>
explicit persistent_segment_tree(Args &&...args) {
std::vector<T> a(args...);
n = static_cast<int>(a.size());
st.reserve(n << 1); lc.reserve(n << 1); rc.reserve(n << 1);
root = build(0, n, a);
}
int original_root() const { return root; }
T query(int rt, int l, int r) const { return query(rt, 0, n, l, r); }
T query(int rt, int l) const { return query(rt, l, l); }
int update(int rt, int pos, const T &val) { return update(rt, 0, n, pos, val); }
int size() const { return n; }
private:
int n, root;
std::vector<T> st;
std::vector<int> lc, rc;
int build(int cl, int cr, const std::vector<T> &a) {
if (cl + 1 == cr) {
st.push_back(a[cl]); lc.push_back(0); rc.push_back(0);
return static_cast<int>(st.size()) - 1;
}
int cm = (cl + cr) >> 1;
int tmp_l = build(cl, cm, a), tmp_r = build(cm, cr, a);
lc.push_back(tmp_l); rc.push_back(tmp_r);
st.push_back(_Sg::op(st[tmp_l], st[tmp_r]));
return static_cast<int>(st.size()) - 1;
}
T query(int idx, int cl, int cr, int l, int r) const {
if (l <= cl && cr <= r + 1) return st[idx];
int cm = (cl + cr) >> 1;
if (r < cm) return query(lc[idx], cl, cm, l, r);
if (l >= cm) return query(rc[idx], cm, cr, l, r);
return _Sg::op(query(lc[idx], cl, cm, l, r), query(rc[idx], cm, cr, l, r));
}
int update(int idx, int cl, int cr, int pos, const T &val) {
if (cl + 1 == cr) {
st.push_back(val); lc.push_back(0); rc.push_back(0);
return static_cast<int>(st.size()) - 1;
}
int cm = (cl + cr) >> 1;
int tmp_l = lc[idx], tmp_r = rc[idx];
if (pos < cm) tmp_l = update(lc[idx], cl, cm, pos, val);
else tmp_r = update(rc[idx], cm, cr, pos, val);
lc.push_back(tmp_l); rc.push_back(tmp_r);
st.push_back(_Sg::op(st[tmp_l], st[tmp_r]));
return static_cast<int>(st.size()) - 1;
}
};
template<typename _Sg> using persistent_segtree = persistent_segment_tree<_Sg>;
template<typename _Sg> using psegtree = persistent_segtree<_Sg>;
constexpr int INF = 0x3f3f3f3f;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q; cin >> n >> q;
vector<int> p(n + 1);
vector< vector<int> > mp((int) 2e5 + 5);
for (int i = 1; i <= n; i++) cin >> p[i], mp[p[i]].push_back(i);
psegtree< addition<int> > st(n + 1, 0);
vector<int> roots((int) 2e5 + 5); roots[(int) 2e5 + 1] = st.original_root();
for (int i = (int) 2e5; i >= 0; i--) {
roots[i] = roots[i + 1];
for (auto &idx : mp[i]) roots[i] = st.update(roots[i], idx, 1);
}
while (q--) {
int l, r; cin >> l >> r;
int lo = 1, hi = n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (st.query(roots[mid], l, r + 1) >= mid) {
lo = mid;
} else {
hi = mid - 1;
}
}
cout << lo << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
