This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//記得跳題
#pragma GCC optimize("O3,unroll_loops")
#pragma GCC target("avx2")
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>
#include<random>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define INF (ll)(4e18)
#define pb push_back
#define mp make_pair
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
ll a[100005];
int t[100005], x[100005], y[100005], n, q;
void sub1() {
FOR(i, 0, q) {
if (t[i] == 1) {
a[x[i]] = y[i];
} else {
int ans = 0;
ll inia = a[x[i] - 1], inib = a[y[i] + 1];
a[x[i] - 1] = a[y[i] + 1] = INF;
ll maxn = 0;
FOR(j, x[i], y[i] + 1) {
maxn = max(maxn, a[j]);
}
FOR(j, x[i], y[i] + 1) {
int l = j - 1, r = j + 1;
ll now = a[j];
while (1) {
if (a[l] > now && a[r] > now) break;
if (a[l] <= now) {
now += a[l]; l--;
}
if (a[r] <= now) {
now += a[r]; r++;
}
}
if (now >= maxn) {
ans++;
}
}
cout << ans << endl;
a[x[i] - 1] = inia;
a[y[i] + 1] = inib;
}
}
}
ll maxn[400005];
void build(int id, int l, int r) {
if (l == r) {
maxn[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
maxn[id] = max(maxn[id << 1], maxn[id << 1 | 1]);
}
int ask(int id, int l, int r, int L, int R, ll x, int t) {
if (maxn[id] < x) return (t ? n + 1 : 0);
if (l > R || r < L) {
return (t ? n + 1 : 0);
}
if (l == r) return l;
if (L <= l && r <= R) {
int mid = (l + r) >> 1;
if (t) {
if (maxn[id << 1] <= x) {
return ask(id << 1 | 1, mid + 1, r, L, R, x, t);
} else {
return ask(id << 1, l, mid, L, R, x, t);
}
} else {
if (maxn[id << 1 | 1] <= x) {
return ask(id << 1, l, mid, L, R, x, t);
} else {
return ask(id << 1 | 1, mid + 1, r, L, R, x, t);
}
}
}
int mid = (l + r) >> 1;
if (t) return min(ask(id << 1, l, mid, L, R, x, t), ask(id << 1 | 1, mid + 1, r, L, R, x, t));
else return max(ask(id << 1, l, mid, L, R, x, t), ask(id << 1 | 1, mid + 1, r, L, R, x, t));
}
ll pre[100005];
void sub2() {
build(1, 1, n);
ll maxn = 0, ans = 0;
FOR(i, 1, n+1) {
maxn = max(maxn, a[i]);
pre[i] = pre[i-1] + a[i];
}
pre[n+1] = pre[n];
FOR(i, 1, n+1) {
int l = i - 1, r = i + 1;
ll now = a[i];
while (1) {
int nl = ask(1, 1, n, 1, l ,now, 0), nr = ask(1, 1, n, r, n, now, 1);
now += pre[l] - pre[nl];
now += pre[nr - 1] - pre[r - 1];
if (now >= maxn) {
ans++;
break;
}
if (now < a[nl] && now < a[nr]) break;
if (a[nl] <= a[nr]) {
if (now >= a[nl]) {
now += a[nl];
l = nl - 1;
l = max(0, l);
} else {
l = nl;
}
if (now >= a[nr]) {
now += a[nr];
r = nr + 1;
r = min(n+1, r);
} else {
r = nr;
}
} else {
if (now >= a[nr]) {
now += a[nr];
r = nr + 1;
r = min(n+1, r);
} else {
r = nr;
}
if (now >= a[nl]) {
now += a[nl];
l = nl - 1;
l = max(0, l);
} else {
l = nl;
}
}
}
//cout << "now = " << now << endl;
}
cout << ans << endl;
}
signed main() {
AC;
// plz
cin >> n;
FOR(i, 1, n+1) cin >> a[i];
cin >> q;
FOR(i, 0, q) cin >> t[i] >> x[i] >> y[i];
a[0] = a[n+1] = INF;
if (n <= 0 && q <= 500) {
sub1();
} else if (q == 1) {
sub2();
}
}
Compilation message (stderr)
fish2.cpp:2:39: warning: bad option '-funroll_loops' to pragma 'optimize' [-Wpragmas]
2 | #pragma GCC optimize("O3,unroll_loops")
| ^
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
3 | #pragma GCC target("avx2")
| ^
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |