이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "sequence.h"
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;
const int MXN = 5e5;
vector<int> ct[MXN + 1];
int pref[4 * MXN + 10], pref1[4 * MXN + 10], suff[4 * MXN + 10], suff1[4 * MXN + 10], sm[4 * MXN + 10], arr[MXN + 1];
void merge(int c, int a, int b) {
pref[c] = max(pref[a], sm[a] + pref[b]);
pref1[c] = min(pref1[a], sm[a] + pref1[b]);
suff[c] = max(suff[b], sm[b] + suff[a]);
suff1[c] = min(suff1[a], sm[b] + suff1[a]);
sm[c] = sm[a] + sm[b];
}
void build(int lf, int rg, int nd) {
if(lf == rg) {
if(arr[lf] == 0) pref[nd] = suff[nd] = sm[nd] = 0;
else pref[nd] = suff[nd] = sm[nd] = 1;
} else {
int mid = (lf + rg) / 2;
build(lf, mid, 2*nd+1);
build(mid+1, rg, 2*nd+2);
merge(nd, 2*nd+1, 2*nd+2);
}
}
void upd(int lf, int rg, int nd, int pos, int v) {
if(lf == rg) {
pref[nd] = suff[nd] = sm[nd] = v;
} else {
int mid = (lf + rg) / 2;
if(pos <= mid) upd(lf, mid, 2*nd+1, pos, v);
else upd(mid+1, rg, 2*nd+2, pos, v);
merge(nd, 2*nd+1, 2*nd+2);
}
}
pair<int, pair<int, int> > qry(int lf, int rg, int nd, int clf, int crg, int v) {
if(clf > rg || lf > crg) return make_pair(0, make_pair(0, 0));
if(clf <= lf && rg <= crg) {
return make_pair(sm[nd], make_pair(pref[nd], suff[nd]));
} else {
int mid = (lf + rg) / 2;
pair<int, pair<int, int> > a, b;
a = qry(lf, mid, 2*nd+1, clf, crg, v);
b = qry(mid+1, rg, 2*nd+2, clf, crg, v);
if(v) return make_pair(a.fi + b.fi, make_pair(max(a.se.fi, a.fi + b.se.fi), max(b.se.se, a.se.se + b.fi)));
else return make_pair(a.fi + b.fi, make_pair(min(a.se.fi, a.fi + b.se.fi), min(b.se.se, a.se.se + b.fi)));
}
}
int N1;
int fen[500001];
void add(int a, int b) {
while(a <= N1) {
fen[a] += b;
a += a&(-a);
}
}
int qy(int a) {
int as = 0;
while(a > 0) {
as += fen[a];
a -= a&(-a);
}
return as;
}
bool cek(int a, int b) {
pair<int, pair<int, int> > d, e, f;
d = qry(0, N1-1, 0, a, b, 0);
// cout<<"D : "<<a<<" "<<b<<" "<<d.fi<<" "<<d.se.fi<<" "<<d.se.se<<endl;
int lr = qy(b + 1) - qy(a);
if(lr >= abs(d.fi)) return 1;
else {
if(d.fi < 0) {
d.fi += qry(0, N1 - 1, 0, 0, a-1, 1).se.se + qry(0, N1-1, 0, b+1, N1-1, 1).se.fi;
} else {
d.fi += qry(0, N1-1, 0, 0, a-1, 0).se.se + qry(0, N1-1, 0, b+1, N1-1, 0).se.fi;
}
if(lr >= abs(d.fi)) return 1;
else return 0;
}
return 0;
}
int sequence(int N, vector<int> A) {
N1 = N;
map<int, int> mp;
for(int i=0;i<N;i++) mp[A[i]] = 1;
int cnt = 0;
for(auto p : mp) mp[p.fi] = cnt++;
for(int i=0;i<N;i++) {
arr[i] = mp[A[i]];
if(arr[i] > 0) add(i, 1);
ct[arr[i]].push_back(i);
}
build(0, N-1, 0);
int ans = 0;
for(int i=0;i<cnt;i++) {
int r = 0;
for(int k=0;k<ct[i].size();k++) {
// cout<<i<<" "<<k<<" "<<r<<endl;
// if(i == 1 && r < ct[i].size()) cout<<r<<" "<<cek(ct[i][k], ct[i][r])<<endl;
while(r < ct[i].size() && cek(ct[i][k], ct[i][r])) {
r++;
// cout<<"r : "<<r<<endl;
}
// cout<<"i : "<<i<<" "<<k<<" "<<r<<endl;
ans = max(ans, r - k);
}
for(int d=0;d<ct[i].size();d++) {
upd(0, N-1, 0, ct[i][d], -1);
add(ct[i][d] + 1, -1);
}
for(int d=0;d<ct[i+1].size();d++) {
upd(0, N-1, 0, ct[i+1][d], 0);
add(ct[i+1][d] + 1, 1);
}
// cout<<qry(0, N-1, 0, 0, N-1, 0).fi<<endl;
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:111:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int k=0;k<ct[i].size();k++) {
| ~^~~~~~~~~~~~~
sequence.cpp:114:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | while(r < ct[i].size() && cek(ct[i][k], ct[i][r])) {
| ~~^~~~~~~~~~~~~~
sequence.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int d=0;d<ct[i].size();d++) {
| ~^~~~~~~~~~~~~
sequence.cpp:125:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int d=0;d<ct[i+1].size();d++) {
| ~^~~~~~~~~~~~~~~
# | 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... |