이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second
int a[500100];
int s1[500100], s2[500100], c[500100];
struct node{
pii x={1e9, -1e9};
node *l = nullptr, *r = nullptr;
node(){}
};
node *t = new node();
void upd(node *v, int l, int r, int pos, int x){
if(l == r){
v -> x = {min(v -> x.ff, x), max(v -> x.ss, x)};
return;
}
int mid = floor(((double)l + (double)r) / 2);
if(mid >= pos){
if(!v -> l) v->l = new node();
upd(v -> l, l, mid, pos, x);
}
else{
if(!v -> r) v->r = new node();
upd(v->r, mid+1, r, pos, x);
}
v -> x = {1e9, -1e9};
if(v -> l) v -> x = {min(v -> x.ff, v -> l -> x.ff), max(v -> x.ss, v -> l -> x.ss)};
if(v -> r) v -> x = {min(v -> x.ff, v -> r -> x.ff), max(v -> x.ss, v -> r -> x.ss)};
}
pii get(node *v, int l, int r, int L, int R){
if(r < L or R < l){
return {1e9, -1e9};
}
if(L <= l and r <= R){
return v -> x;
}
int mid=floor(((double)l + (double)r) / 2);
pii x = {1e9, -1e9};
if(v -> l){
pii k = get(v -> l, l, mid, L, R);
x = {min(x.ff, k.ff), max(x.ss, k.ss)};
}
if(v -> r){
pii k = get(v -> r, mid + 1, r, L, R);
x = {min(x.ff, k.ff), max(x.ss, k.ss)};
}
return x;
}
int sequence(int n, vector<int> A) {
int ans = 0;
for(int i=1; i<=n; i++){
a[i] = A[i - 1];
}
for(int x=1; x<=n; x++){
vector<pii> q;
int mn=0, mx=0, sum=0;
for(int i=1; i<=n; i++){
if(a[i] == x){
q.pb({mn, mx});
mn = 1e9;
mx = -1e9;
}
if(a[i] > x){
sum += 1;
}
if(a[i] < x){
sum -= 1;
}
mn = min(mn, sum);
mx = max(mx, sum);
}
q.pb({mn, mx});
vector<pair<pii, int> > zap;
for(int i=0; i<q.size(); i++){
zap.pb({{q[i].ss + i, q[i].ff-i}, i});
}
vector<pair<pii, int> > h;
for(int i=0; i<q.size(); i++){
h.pb({{q[i].ff+i, q[i].ss-i}, i});
}
sort(h.begin(), h.end());
sort(zap.begin(), zap.end());
int ls = 0;
t = new node();
int d = n + 1;
for(int i=0; i<zap.size(); i++){
int L=zap[i].ff.ff, R=zap[i].ff.ss;
while(ls < h.size() and h[ls].ff.ff <= L){
upd(t, d - n, d + n, h[ls].ff.ss + d, h[ls].ss);
ls++;
}
pii dd = get(t, d-n, d+n, d+R, d+n);
ans = max(ans, max(zap[i].ss - dd.ff, dd.ss - zap[i].ss));
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i=0; i<q.size(); i++){
| ~^~~~~~~~~
sequence.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=0; i<q.size(); i++){
| ~^~~~~~~~~
sequence.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i=0; i<zap.size(); i++){
| ~^~~~~~~~~~~
sequence.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | while(ls < h.size() and h[ls].ff.ff <= L){
| ~~~^~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |