| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 679521 |
2023-01-08T12:47:50 Z |
elkernos |
Fish 2 (JOI22_fish2) |
C++17 |
|
4000 ms |
15232 KB |
// while (clock()<=69*CLOCKS_PER_SEC)
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("O3")
// #pragma GCC target ("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x) \
sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
{
sim > struct rge {
c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
~debug()
{
cerr << endl;
}
eni(!=) cerr << boolalpha << i;
ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
ris << "" << d.first << " --> " << d.second << "";
}
sim dor(rge<c> d)
{
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c &)
{
ris;
}
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#ifdef XOX
#warning Times may differ!!!
#endif
#define endl '\n'
#define pb emplace_back
#define vt vector
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int nax = 100 * 1007;
const ll oo = 1e17;
int n;
#define lc 2 * v
#define rc 2 * v + 1
#define m (l + r) / 2
struct CMin {
struct Node {
pii p = {0, 1};
int lazy = 0;
void dod(int x)
{
p.first += x;
lazy += x;
}
};
Node nothing = {{n + 5, 0}, 0};
friend Node operator+(const Node &l, const Node &r)
{
Node ret;
ret.p = min(l.p, r.p);
if (l.p.first == r.p.first) ret.p.second = l.p.second + r.p.second;
return ret;
}
Node tree[4 * nax];
void push(int v)
{
for (auto to : {lc, rc})
tree[to].dod(tree[v].lazy);
tree[v].lazy = 0;
}
void build(int v = 1, int l = 0, int r = n + 1)
{
if (l == r) {
tree[v].p.second = 1;
return;
}
build(lc, l, m), build(rc, m + 1, r);
tree[v] = tree[lc] + tree[rc];
}
void add(int ql, int qr, int x, int v = 1, int l = 0, int r = n + 1)
{
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
tree[v].dod(x);
return;
}
push(v);
add(ql, qr, x, lc, l, m);
add(ql, qr, x, rc, m + 1, r);
tree[v] = tree[lc] + tree[rc];
}
Node query(int ql, int qr, int v = 1, int l = 0, int r = n + 1)
{
if (r < ql || qr < l) return nothing;
if (ql <= l && r <= qr) return tree[v];
push(v);
return query(ql, qr, lc, l, m) +
query(ql, qr, rc, m + 1, r);
}
};
struct Sum {
typedef ll T;
static constexpr T unit = 0;
T f(T a, T b) { return a + b; } // (any associative fn)
vector<T> s;
int n;
Sum(int nd = nax, T def = unit) : s(2 * nd, def), n(nd) {}
void update(int pos, T val)
{
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int b, int e)
{
T ra = unit, rb = unit;
for (b += n, e += n + 1; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
struct Max {
ll tree[4 * nax];
void update(int pos, ll to, int v = 1, int l = 0, int r = n + 1)
{
if (pos < l || r < pos) return;
if (l == r) {
tree[v] = to;
return;
}
update(pos, to, lc, l, m);
update(pos, to, rc, m + 1, r);
tree[v] = max(tree[lc], tree[rc]);
}
int maxPrawo(int ogr, ll od, int v = 1, int l = 0, int r = n + 1)
{
if (tree[v] <= od) return -1;
if (l == r) return l;
if (ogr <= m) return maxPrawo(ogr, od, lc, l, m);
int ret = maxPrawo(ogr, od, rc, m + 1, r);
return ret != -1 ? ret : maxPrawo(ogr, od, lc, l, m);
}
int maxLewo(int ogr, ll od, int v = 1, int l = 0, int r = n + 1)
{
if (tree[v] <= od) return -1;
if (l == r) return l;
if (m < ogr) return maxLewo(ogr, od, rc, m + 1, r);
int ret = maxLewo(ogr, od, lc, l, m);
return ret != -1 ? ret : maxLewo(ogr, od, rc, m + 1, r);
}
};
int main()
{
cin.tie(0)->sync_with_stdio(0);
CMin intervals;
Sum getsum;
Max getmax;
cin >> n;
vt<ll> a(n + 2);
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = a[n + 1] = oo;
for (int i = 0; i <= n + 1; i++) {
getsum.update(i, a[i]);
getmax.update(i, a[i]);
}
intervals.build();
set<pair<int, int>> alive;
auto good = [&](int l, int r) {
if (r - l + 1 <= 2) return false;
return getsum.query(l + 1, r - 1) < min(a[l], a[r]);
};
auto wsadz = [&](int l, int r, int x) {
if (x == +1) {
if (!alive.count({l, r})) {
debug() << imie(l) imie(r) imie(x);
alive.emplace(l, r);
intervals.add(l + 1, r - 1, +1);
}
}
if (x == -1) {
if (alive.count({l, r})) {
debug() << imie(l) imie(r) imie(x);
alive.erase({l, r});
intervals.add(l + 1, r - 1, -1);
}
}
};
auto wezL = [&](int l, int r) {
return getmax.maxPrawo(l - 1, getsum.query(l, r - 1));
};
auto wezR = [&](int l, int r) {
return getmax.maxLewo(r + 1, getsum.query(l + 1, r));
};
auto findboth = [&](int p, int x) {
int l = p - 1, r = p + 1;
while (1) {
if (good(l, r)) wsadz(l, r, x);
if (l == 0 && r == n + 1) break;
if (a[l] < a[r]) l = wezL(l, r);
else r = wezR(l, r);
}
};
auto findpresuf = [&](int p, int x) {
int r = wezR(p, p);
while (1) {
if (good(p, r)) wsadz(p, r, x);
if (r == n + 1) break;
r = wezR(p, r);
}
int l = wezL(p, p);
while (1) {
if (good(l, p)) wsadz(l, p, x);
if (l == 0) break;
l = wezL(l, p);
}
};
for (int i = 1; i <= n; i++) {
findboth(i, +1);
findpresuf(i, +1);
}
int q;
cin >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int i, x;
cin >> i >> x;
findboth(i, -1);
findpresuf(i, -1);
a[i] = x;
getsum.update(i, x);
getmax.update(i, x);
findboth(i, +1);
findpresuf(i, +1);
}
else {
int l, r;
cin >> l >> r;
int real_l = l, real_r = r;
int lp = l + 1, rp = r - 1;
while (lp <= r) {
if (getsum.query(l, lp - 1) < a[lp]) {
real_l = lp;
}
lp++;
}
while (l <= rp) {
if (getsum.query(rp + 1, r) < a[rp]) {
real_r = rp;
}
rp--;
}
cout << intervals.query(real_l, real_r).p.second << endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9784 KB |
Output is correct |
| 5 |
Incorrect |
17 ms |
9812 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
693 ms |
15180 KB |
Output is correct |
| 3 |
Correct |
953 ms |
14508 KB |
Output is correct |
| 4 |
Correct |
712 ms |
15196 KB |
Output is correct |
| 5 |
Correct |
923 ms |
14492 KB |
Output is correct |
| 6 |
Correct |
225 ms |
13552 KB |
Output is correct |
| 7 |
Correct |
606 ms |
11980 KB |
Output is correct |
| 8 |
Correct |
221 ms |
13516 KB |
Output is correct |
| 9 |
Correct |
596 ms |
12000 KB |
Output is correct |
| 10 |
Correct |
725 ms |
12924 KB |
Output is correct |
| 11 |
Correct |
926 ms |
12604 KB |
Output is correct |
| 12 |
Correct |
307 ms |
12620 KB |
Output is correct |
| 13 |
Correct |
368 ms |
12820 KB |
Output is correct |
| 14 |
Correct |
274 ms |
14288 KB |
Output is correct |
| 15 |
Correct |
292 ms |
14268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9784 KB |
Output is correct |
| 5 |
Incorrect |
17 ms |
9812 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
693 ms |
15180 KB |
Output is correct |
| 3 |
Correct |
953 ms |
14508 KB |
Output is correct |
| 4 |
Correct |
712 ms |
15196 KB |
Output is correct |
| 5 |
Correct |
923 ms |
14492 KB |
Output is correct |
| 6 |
Correct |
225 ms |
13552 KB |
Output is correct |
| 7 |
Correct |
606 ms |
11980 KB |
Output is correct |
| 8 |
Correct |
221 ms |
13516 KB |
Output is correct |
| 9 |
Correct |
596 ms |
12000 KB |
Output is correct |
| 10 |
Correct |
725 ms |
12924 KB |
Output is correct |
| 11 |
Correct |
926 ms |
12604 KB |
Output is correct |
| 12 |
Correct |
307 ms |
12620 KB |
Output is correct |
| 13 |
Correct |
368 ms |
12820 KB |
Output is correct |
| 14 |
Correct |
274 ms |
14288 KB |
Output is correct |
| 15 |
Correct |
292 ms |
14268 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 17 |
Execution timed out |
4072 ms |
14520 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
693 ms |
15180 KB |
Output is correct |
| 3 |
Correct |
953 ms |
14508 KB |
Output is correct |
| 4 |
Correct |
712 ms |
15196 KB |
Output is correct |
| 5 |
Correct |
923 ms |
14492 KB |
Output is correct |
| 6 |
Correct |
225 ms |
13552 KB |
Output is correct |
| 7 |
Correct |
606 ms |
11980 KB |
Output is correct |
| 8 |
Correct |
221 ms |
13516 KB |
Output is correct |
| 9 |
Correct |
596 ms |
12000 KB |
Output is correct |
| 10 |
Correct |
725 ms |
12924 KB |
Output is correct |
| 11 |
Correct |
926 ms |
12604 KB |
Output is correct |
| 12 |
Correct |
307 ms |
12620 KB |
Output is correct |
| 13 |
Correct |
368 ms |
12820 KB |
Output is correct |
| 14 |
Correct |
274 ms |
14288 KB |
Output is correct |
| 15 |
Correct |
292 ms |
14268 KB |
Output is correct |
| 16 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 17 |
Execution timed out |
4064 ms |
15232 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 4 |
Correct |
5 ms |
9784 KB |
Output is correct |
| 5 |
Incorrect |
17 ms |
9812 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
