| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 589622 | nguyen31hoang08minh2003 | Poklon (COCI17_poklon) | C++14 | 1113 ms | 43168 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+
|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|-\/\/-|
|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|\/\/\/|
|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|/-/\-\|
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+
|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|\-\/-/|
|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|/\/\/\|
|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|-/\/\-|
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (signed i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (signed i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (signed i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
class SegmentTree {
private:
int n;
std::vector<int> it;
void modify(const int q, const int val, const int i, const int l, const int r) {
if (q < l || r < q)
return;
if (l == r) {
it[i] = val;
return;
}
const int m = l + r >> 1;
modify(q, val, i << 1, l, m);
modify(q, val, i << 1 | 1, m + 1, r);
it[i] = it[i << 1] + it[i << 1 | 1];
}
void update(const int q, const int val, const int i, const int l, const int r) {
if (q < l || r < q)
return;
it[i] += val;
if (l == r)
return;
const int m = l + r >> 1;
update(q, val, i << 1, l, m);
update(q, val, i << 1 | 1, m + 1, r);
}
int query(const int ql, const int qr, const int i, const int l, const int r) const {
if (qr < l || r < ql)
return 0;
if (ql <= l && r <= qr)
return it[i];
const int m = l + r >> 1;
return query(ql, qr, i << 1, l, m) + query(ql, qr, i << 1 | 1, m + 1, r);
}
void build(const int i, const int l, const int r) {
if (l == r) {
it[i] = 0;
return;
}
const int m = l + r >> 1;
build(i << 1, l, m);
build(i << 1 | 1, m + 1, r);
it[i] = it[i << 1] + it[i << 1 | 1];
}
public:
SegmentTree(): n(0) {};
SegmentTree(const int n): n(n), it(n + 5 << 2) {};
void resize(int m) {
n = m;
m = n + 5 << 2;
it.resize(m);
}
void reload() {
std::fill(it.begin(), it.end(), 0);
}
void modify(const int q, const int val) {
modify(q, val, 1, 1, n);
}
void update(const int q, const int val) {
update(q, val, 1, 1, n);
}
int query(const int ql, const int qr) const {
return query(ql, qr, 1, 1, n);
}
void build() {
build(1, 1, n);
}
};
#define maxN 500005
#define maxQ 500005
vi p, f;
int n, q;
array<int, maxN> a, g[3];
array<int, maxQ> l, r, d[3];
void input() {
cin >> n >> q;
p.resize(n);
f.resize(q);
fort(i, 1, n) {
cin >> a[i];
p[i - 1] = i;
}
fore(i, 0, q) {
cin >> l[i] >> r[i];
f[i] = i;
}
}
void solve() {
SegmentTree it(n);
sort(all(p), [&](const int &l, const int &r) -> bool {
if (a[l] != a[r])
return a[l] < a[r];
return l < r;
});
sort(all(f), [&](const int &x, const int &y) -> bool {
return l[x] < l[y];
});
g[0][p.front()] = -1;
fore(i, 1, n)
if (a[p[i - 1]] != a[p[i]])
g[0][p[i]] = -1;
else
g[0][p[i]] = p[i - 1];
fort(x, 1, 2)
fort(y, 1, n) {
if (g[x - 1][y] < 0) {
g[x][y] = -1;
continue;
}
g[x][y] = g[0][g[x - 1][y]];
}
for (int j, z = 0; z <= 2; ++z) {
sort(all(p), [&](const int &x, const int &y) -> bool {
return g[z][x] < g[z][y];
});
j = 0;
for (const int &i : f) {
for (; j < n && g[z][p[j]] < l[i]; ++j)
it.update(p[j], 1);
d[z][i] = it.query(l[i], r[i]);
}
it.reload();
}
fore(i, 0, q)
cout << d[1][i] - d[0][i] - (d[2][i] - d[1][i]) << '\n';
}
int main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
input();
solve();
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||