#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }
const int INF = 1000 * 1000 * 1000;
struct Seg {
int n;
vii p1;
vii p2;
Seg(int n, vii &vals) {
this->n = n;
p1.resize(4 * n);
p2.resize(4 * n);
build(vals);
}
bool can(ii pl, ii pr) {
return pl.S <= pr.F;
}
void pull(int v) {
int lc = 2 * v, rc = 2 * v + 1;
if(can(p1[lc], p1[rc])) {
p1[v] = {p1[lc].F, p1[rc].S};
} else if(can(p1[lc], p2[rc])) {
p1[v] = {p1[lc].F, p2[rc].S};
} else {
p1[v] = {-1, INF};
}
if(can(p2[lc], p1[rc])) {
p2[v] = {p2[lc].F, p1[rc].S};
} else if(can(p2[lc], p2[rc])) {
p2[v] = {p2[lc].F, p2[rc].S};
} else {
p2[v] = {-1, INF};
}
}
void build(vii &vals, int v = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = n - 1;
if(tl == tr) {
p1[v] = {vals[tl].F, vals[tl].F};
p2[v] = {vals[tl].S, vals[tl].S};
return;
}
int tm = (tl + tr) / 2;
build(vals, 2 * v, tl, tm);
build(vals, 2 * v + 1, tm + 1, tr);
pull(v);
}
void set(int p, ii val, int v = 1, int tl = 0, int tr = -1) {
if(tr == -1) tr = n - 1;
if(tl == tr) {
p1[v] = {val.F, val.F};
p2[v] = {val.S, val.S};
return;
}
int tm = (tl + tr) / 2;
if(p <= tm)
set(p, val, 2 * v, tl, tm);
else
set(p, val, 2 * v + 1, tm + 1, tr);
pull(v);
}
bool is_increasing() {
return p1[1].F != -1;
}
};
int solve_lin(vi &a) {
int n = sz(a);
vii vals;
forn(i, n) {
vals.eb(a[i], i);
}
sort(all(vals));
int mx = 0;
forn(i, n) {
maxeq(mx, vals[i].S - i);
}
return mx;
}
void solve() {
int n, q;
cin >> n >> q;
vi a(n);
forn(i, n)
cin >> a[i];
forn(_, q) {
int x, v;
cin >> x >> v;
a[x] = v;
cout << solve_lin(a) << '\n';
}
}
vi countScans(vi a, vi x, vi v) {
int n = sz(a);
vi ans(n);
forn(i, n) {
a[x[i]] = v[i];
ans[i] = solve_lin(a);
}
return ans;
}
//int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
//
//// freopen("optmilk.in", "r", stdin);
//// freopen("optmilk.out", "w", stdout);
//
// int t = 1;
//// cin >> t;
// while(t--) {
// solve();
// }
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5102 ms |
1520 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
