글 읽기 - 출력초과

(追記) (追記ここまで)

출력초과

13548번 - 수열과 쿼리 6

cbs0615 7년 전 0

안녕하세요. 평범한 MO's algorithm문제를 풀고있었는데

26-29번째 줄을 보시면

maxx = maxx-1 이나 maxx-- 로하면 출력초과를

maxx=c-1 로하면 AC를 받습니다.

어디서 문제가 일어나는 것일까요..

#include <bits/stdc++.h>
using namespace std;
class triple
{
public:
 int x, y, z;
};
int n, m, sn, arr[100005], cnt[100005], fa[100005], maxx;
triple q[100005];
void add(int c)
{
 fa[c]--;
 fa[c+1]++;
 maxx=max(maxx, c+1);
}
void del(int c)
{
 fa[c]--;
 fa[c-1]++;
 if(fa[c]==0 && maxx==c)
 {
 //maxx = maxx-1; 출력초과
 //maxx=c-1; AC
 maxx=c-maxx;
 maxx+=c-1; // AC
 }
}
int main()
{
 ios::sync_with_stdio(false);
 cin.tie(nullptr);
 cin>>n;
 for(int i=0;i<n;i++) cin>>arr[i];
 cin>>m;
 for(int i=0;i<m;i++)
 {
 cin>>q[i].x>>q[i].y;
 q[i].z=i;
 q[i].x--;q[i].y--;
 }
 int sn=sqrt(n);
 sort(q, q+m, [&sn](triple& a, triple& b)
 {
 if(a.x/sn == b.x/sn) return a.y < b.y;
 return a.x/sn < b.x/sn;
 });
 int answer[100005], ret[100005];
 for(int i=q[0].x;i<=q[0].y;i++)
 {
 add(cnt[arr[i]]);
 cnt[arr[i]]++;
 }
 answer[0]=maxx;
 for(int i=1;i<m;i++)
 {
 if(q[i].x > q[i-1].x)
 {
 // del
 for(int j=q[i-1].x;j<q[i].x;j++)
 {
 del(cnt[arr[j]]);
 cnt[arr[j]]--;
 }
 }
 else if(q[i].x < q[i-1].x)
 {
 for(int j=q[i].x;j<q[i-1].x;j++)
 {
 add(cnt[arr[j]]);
 cnt[arr[j]]++;
 }
 }
 if(q[i].y > q[i-1].y)
 {
 for(int j=q[i-1].y+1;j<=q[i].y;j++)
 {
 add(cnt[arr[j]]);
 cnt[arr[j]]++;
 }
 }
 else if(q[i].y < q[i-1].y)
 {
 for(int j=q[i].y+1;j<=q[i-1].y;j++)
 {
 del(cnt[arr[j]]);
 cnt[arr[j]]--;
 }
 }
 answer[i] = maxx;
 }
 for(int i=0;i<m;i++)
 {
 ret[q[i].z]=answer[i];
 }
 for(int i=0;i<m;i++)
 {
 cout << ret[i] << '\n';
 }
 return 0;
}

cbs0615 7년 전 0

그냥 운좋게 맞은거였네요 ..

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

출력초과

cbs0615 7년 전 0

cbs0615 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말