// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int N,m,q;
struct Node {
int mn, mx, tag;
Node() : mn(INF), mx(-INF), tag(0) {};
Node(int v) : mn(v), mx(v), tag(0) {};
Node merge(Node &oth) {
Node ret;
ret.mx = max(oth.mx, mx);
ret.mn = min(oth.mn, mn);
return ret;
}
void add(int x) {
mn += x;
mx += x;
tag += x;
}
};
struct SegTree {
vector<Node> data;
int sz;
SegTree() : sz(0) {}
void reset(int s) {
sz = s;
data.assign(4*(sz + 3), Node());
}
void push(int v) {
data[v<<1].add(data[v].tag);
data[v<<1^1].add(data[v].tag);
data[v].tag = 0;
}
void build(int tl, int tr, int v, vector<int> &vec) {
if(tl == tr) {
data[v] = Node(vec[tl]);
return;
}
int tm = (tl + tr) >> 1;
build(tl, tm, v<<1, vec);
build(tm + 1, tr, v<<1^1, vec);
data[v] = data[v<<1].merge(data[v<<1^1]);
}
int getMin(int tl, int tr, int v, int l, int r) {
if(tl >= l && tr <= r) {
return data[v].mn;
}
if(tl > r || tr < l) return INF;
int tm = (tl + tr) >> 1;
push(v);
return min(getMin(tl, tm, v<<1, l, r), getMin(tm + 1, tr, v<<1^1, l, r));
}
int getMin(int l, int r) {
l = max(0, l); r = min(sz, r);
if(l > r) {
// cout<<"MIN:"<<l<<" "<<r<<" val:"<<0<<"\n";
return 0;
}
// cout<<"MIN:"<<l<<" "<<r<<" val:"<<getMin(0, sz, 1, l, r)<<"\n";
return getMin(0, sz, 1, l, r);
}
int getMax(int tl, int tr, int v, int l, int r) {
if(tl >= l && tr <= r) {
return data[v].mx;
}
if(tl > r || tr < l) return -INF;
int tm = (tl + tr) >> 1;
push(v);
return max(getMax(tl, tm, v<<1, l, r), getMax(tm + 1, tr, v<<1^1, l, r));
}
int getMax(int l, int r) {
l = max(0, l); r = min(sz, r);
if(l > r) {
// cout<<"MAX:"<<l<<" "<<r<<" val:"<<0<<"\n";
return 0;
}
// cout<<"MAX:"<<l<<" "<<r<<" val:"<<getMax(0, sz, 1, l, r)<<"\n";
return getMax(0, sz, 1, l, r);
}
void update(int tl, int tr, int v, int l, int r, int val) {
if(tl >= l && tr <= r) {
data[v].add(val);
return;
}
if(tl > r || tr < l) {
return;
}
int tm = (tl + tr) >> 1;
push(v);
update(tl, tm, v<<1, l, r, val);
update(tm + 1, tr, v<<1^1, l, r, val);
data[v] = data[v<<1].merge(data[v<<1^1]);
}
void update(int l, int r, int val) {
l = max(0, l); r = min(sz, r);
if(l > r) return;
update(0, sz, 1, l, r, val);
}
};
SegTree st;
vector<vector<int> > occ;
vector<int> pr;
int getSum(int l, int r) {
l = max(0, l); r = min(N - 1, r);
if(l > r) return 0;
return st.getMax(r, r) - (l == 0 ? 0 : st.getMax(l - 1, l - 1));
}
int sequence(int n, vector<int> a) {
N = n;
st.reset(n - 1);
occ.assign(n + 1, vector<int>());
pr.assign(n, 0);
for(int i = 0; i<n; i++) {
occ[a[i]].pb(i);
}
pr[0] = 1;
for(int i = 1; i<n; i++) pr[i] = pr[i - 1] + 1;
st.build(0, n - 1, 1, pr);
for(int i = 1; i<=n; i++) {
for(auto c : occ[i]) {
st.update(c, n - 1, -1);
}
if(occ[i].size() > 1) {
int fir = occ[i][0], sec = occ[i][1];
int mx = st.getMax(sec , n - 1) - min(0, st.getMin(0, fir - 1));
int mn = st.getMin(sec , n - 1) - max(0, st.getMax(0, fir - 1));
// cout<<"i:"<<i<<" mn: "<<mn<<" mx:"<<mx<<"\n";
if(mx >= -2 && mn <= 2) {
return 2;
}
}
for(auto c : occ[i]) {
st.update(c, n - 1, -1);
}
}
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
372 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
372 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
75 ms |
51328 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
372 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
363 ms |
57168 KB |
Output is correct |
2 |
Correct |
418 ms |
56996 KB |
Output is correct |
3 |
Correct |
151 ms |
56604 KB |
Output is correct |
4 |
Correct |
122 ms |
56608 KB |
Output is correct |
5 |
Correct |
261 ms |
53272 KB |
Output is correct |
6 |
Correct |
404 ms |
55060 KB |
Output is correct |
7 |
Correct |
373 ms |
55232 KB |
Output is correct |
8 |
Correct |
247 ms |
54996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
372 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
372 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |