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 Y8o "main"
#define maxn (int) 2e5 + 5
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
//#define f first
//#define s second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
if(fopen(Y8o".inp", "r"))
{
freopen(Y8o".inp", "r", stdin);
// freopen(Y8o".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
int n, Q, cnt;
ll a[maxn], b[maxn], dp[maxn], dapan[maxn][2];
struct dl { int id, l, r; ll x; } qr[maxn];
void sub1()
{
for(int i = 1; i <= n; i ++) b[i] = a[i];
for(int _ = 1; _ <= Q; _ ++)
{
int id = qr[_].id, l = qr[_].l, r = qr[_].r; ll x = qr[_].x;
if(id == 1)
for(int j = l; j <= r; j ++) b[j] += x;
else
{
for(int j = 1; j <= n; j ++) dp[j] = -1e18;
dp[0] = 0;
for(int j = 1; j <= n; j ++)
{
ll mx = -1e18, mi = 1e18;
for(int t = j; t >= 1; t --)
{
mx = max(mx, b[t]), mi = min(mi, b[t]);
dp[j] = max(dp[j], dp[t - 1] + mx - mi);
}
}
cout << dp[n] << '\n';
// dapan[++ cnt][0] = dp[n];
}
}
}
int fake(ll val, vector<ll> &v) {
return lower_bound(v.begin(), v.end(), val) - v.begin() + 1;
}
ll bit1[maxn], bit2[maxn];
void update_up(int x, ll val) { while(x <= n) bit1[x] = max(bit1[x], val), x += (x & -x); }
ll get_dw(int x, ll best = -1e18) { while(x) best = max(best, bit1[x]), x -= (x & -x); return best; }
void update_dw(int x, ll val) { while(x) bit2[x] = max(bit2[x], val), x -= (x & -x); }
ll get_up(int x, ll best = -1e18) { while(x <= n) best = max(best, bit2[x]), x += (x & -x); return best; }
void sub2_1()
{
vector<ll> v;
for(int i = 1; i <= n; i ++) b[i] = a[i], v.push_back(b[i]);
sort(v.begin(), v.end());
for(int _ = 1; _ <= Q; _ ++)
{
int id = qr[_].id, l = qr[_].l, r = qr[_].r; ll x = qr[_].x;
if(id == 1)
{
for(int j = l; j <= r; j ++) b[j] += x;
v.clear();
for(int j = 1; j <= n; j ++) v.push_back(b[j]);
sort(v.begin(), v.end());
}
else
{
for(int j = 1; j <= n; j ++) bit1[j] = bit2[j] = -1e18;
dp[0] = 0;
update_dw(fake(b[1], v) - 1, dp[0] + b[1]);
update_up(fake(b[1], v) + 1, dp[0] - b[1]);
for(int j = 1; j <= n; j ++) {
dp[j] = dp[j - 1];
dp[j] = max(dp[j], get_up(fake(b[j], v)) - b[j] );
dp[j] = max(dp[j], get_dw(fake(b[j], v)) + b[j] );
update_up(fake(b[j + 1], v) + 1, dp[j] - b[j + 1]);
update_dw(fake(b[j + 1], v) - 1, dp[j] + b[j + 1]);
// for(int t = j; t >= 1; t --) {
// dp[j] = max(dp[j], dp[t - 1] + abs(b[j] - b[t]));
// }
}
cout << dp[n] << '\n';
// dapan[++ cnt][1] = dp[n];
}
}
}
void Inp()
{
cin >> n >> Q;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= Q; i ++)
{
int id, l = 0, r = 0; ll x = 0;
cin >> id;
if(id == 1) cin >> l >> r >> x;
qr[i] = {id, l, r, x};
}
}
void Sinh()
{
n = GetRandom(20, 20), Q = GetRandom(20, 20);
cout << n << ' ' << Q << '\n';
for(int i = 1; i <= n ; i++)
{
a[i] = GetRandom(-1e8, 1e8);
cout << a[i] << ' ';
}
cout << '\n';
for(int i = 1; i <= Q; i ++)
{
int id = GetRandom(1, 2), l = GetRandom(1, n), r = GetRandom(1, n), x = GetRandom(-1e8, 1e8);
cout << id << ' ';
if(id == 1) cout << l << ' ' <<r << ' ' << x << '\n';
else cout << '\n';
qr[i] = {id, l, r, x};
}
}
void solve()
{
Inp();
// Sinh();
// sub1(), cnt = 0;
// sub2_1();
// cout << "ANS :" << '\n';
// for(int i = 1; i <= cnt; i ++) cout << dapan[i][0] << ' ' << dapan[i][1] << '\n';
if(max(n, Q) <= 200) sub1();
else if(max(n, Q) <= 3000) sub2_1();
}
int main()
{
iof();
int nTest = 1;
// cin >> nTest;
while(nTest --) {
solve();
}
ctime();
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'void iof()':
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen(Y8o".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |