/**
* \author Nguyen Duc Kien
* \date 20/06/2021
*/
///Task name
#define TASK ""
///-------------------------------------------///
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
int n, Q, f[maxn], g[maxn], ftree[maxn << 2], lftree[maxn << 2];
long long a[maxn];
struct query
{
int req, L, R, S, C;
void inp()
{
cin >> req >> L >> R;
if (req != 3) cin >> S >> C;
}
}q[maxn];
void LazyUpd(int nod)
{
lftree[nod * 2] = lftree[nod * 2 + 1] = lftree[nod];
ftree[nod * 2] = max(ftree[nod * 2], lftree[nod * 2]);
ftree[nod * 2 + 1] = max(ftree[nod * 2 + 1], lftree[nod * 2 + 1]);
lftree[nod] = 0;
}
void Init(int nod, int l, int r)
{
if (l == r)
{
ftree[nod] = f[l];
return;
}
int mid = (l + r) / 2;
Init(nod * 2, l, mid);
Init(nod * 2 + 1, mid + 1, r);
ftree[nod] = max(ftree[nod * 2], ftree[nod * 2 + 1]);
}
void Upd(int nod, int l, int r, int u, int v, int w)
{
if (l > v || r < u) return;
if (l >= u && r <= v)
{
ftree[nod] = w;
lftree[nod] = w;
return;
}
if (lftree[nod]) LazyUpd(nod);
int mid = (l + r) / 2;
Upd(nod * 2, l, mid, u, v, w);
Upd(nod * 2 + 1, mid + 1, r, u, v, w);
ftree[nod] = max(ftree[nod * 2], ftree[nod * 2 + 1]);
}
int Max(int nod, int l, int r, int u, int v)
{
if (l > v || r < u) return 0;
if (l >= u && r <= v) return ftree[nod];
if (lftree[nod]) LazyUpd(nod);
int mid = (l + r) / 2;
int L = Max(nod * 2, l, mid, u, v);
int R = Max(nod * 2 + 1, mid + 1, r, u, v);
return max(L, R);
}
///Shortcuts
void Upd(int u, int v, int w) {Upd(1, 1, n, u, v, w);}
int Max(int u, int v) {return Max(1, 1, n, u, v);}
namespace Sub1
{
void Main()
{
int res = 1;
int d = 2;
a[n + 1] = 1e9 + 69;
for (int i = 2; i <= n; i ++)
{
if (a[i + 1] - a[i] == a[i] - a[i - 1]) d ++;
else res = max(res, d), d = 2;
}
bool f2 = 0;
for (int i = 1; i <= Q; i ++)
{
if (q[i].req == 2) f2 = 1;
else if (q[i].req == 3)
{
if (f2 == 0) cout << res << "\n";
else cout << n << "\n";
}
}
}
}
namespace Sub2
{
void Main()
{
for (int t = 1; t <= Q; t ++)
{
int L = q[t].L;
int R = q[t].R;
int S = q[t].S;
int C = q[t].C;
if (q[t].req == 1)
{
for (int i = L; i <= R; i ++)
a[i] = a[i] + S + 1ll * (i - L) * C;
}
else if (q[t].req == 2)
{
for (int i = L; i <= R; i ++)
a[i] = S + 1ll * (i - L) * C;
}
else
{
int res = 1, cur = 2;
long long d = a[L + 1] - a[L];
for (int i = L + 1; i < R; i ++)
{
if (a[i + 1] - a[i] == d) cur ++;
else
{
res = max(res, cur);
cur = 2;
d = a[i + 1] - a[i];
}
}
res = max(res, cur);
if (L == R) res = 1;
cout << res << "\n";
}
}
}
}
namespace Sub3
{
void Main()
{
g[1] = 1;
g[2] = 2;
for (int i = 2; i < n; i ++)
{
if (a[i + 1] - a[i] == a[i] - a[i - 1]) g[i + 1] = g[i] + 1;
else g[i + 1] = 2;
}
f[n] = 1;
f[n - 1] = 2;
for (int i = n - 1; i > 1; i --)
{
if (a[i - 1] - a[i] == a[i] - a[i + 1]) f[i - 1] = f[i] + 1;
else f[i - 1] = 2;
}
Init(1, 1, n);
for (int t = 1; t <= Q; t ++)
{
int L = q[t].L;
int R = q[t].R;
int res = min(R - L + 1, max(f[L], g[R]));
int l = L + f[L];
int r = R - g[R];
if (l <= r) res = max(res, Max(l, r));
cout << res << "\n";
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cerr << "Processing...\n\n";
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
// freopen(TASK".OUT", "w", stdout);
}
cin >> n >> Q;
for (int i = 1; i <= n; i ++) cin >> a[i];
bool all_1_n = 1;
bool no_change = 1;
for (int i = 1; i <= Q; i ++)
{
q[i].inp();
if (q[i].L != 1 || q[i].R != n) all_1_n = 0;
if (q[i].req != 3) no_change = 0;
}
// if (n <= 1000 && Q <= 1000) Sub2::Main();
// else if (all_1_n) Sub1::Main();
// else if (no_change) Sub3::Main();
Sub3::Main();
cerr << "\n\n-----------------\n";
return 0;
}
Compilation message
Progression.cpp: In function 'int main()':
Progression.cpp:201:10: warning: variable 'all_1_n' set but not used [-Wunused-but-set-variable]
201 | bool all_1_n = 1;
| ^~~~~~~
Progression.cpp:202:10: warning: variable 'no_change' set but not used [-Wunused-but-set-variable]
202 | bool no_change = 1;
| ^~~~~~~~~
Progression.cpp:195:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
195 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
321 ms |
16180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
15980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
260 ms |
15808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
222 ms |
15980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
321 ms |
16180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
