plzrun   3년 전

//펜윅으로하면 부분합이 롱롱범위를 초과하는것 같습니다.
//세그로 다시해보려고 합니다.

//펜윅 그대로 써서 해결했습니다.


오늘 하루종일 붙잡고 있는데 BOJ에서는 21%에서 틀렸다고 하고,

spoj에서는 28번째 테케에서 나가는것 같습니다.


구간 업뎃하는 펜윅트리와 parellel binary search를 이용했습니다.

사실 펜윅트리 부분이 틀렸나 해서 요리조리 바꿔봤는데도 계속 같은곳에서 WA를 받습니다.


아무래도 pbs쪽에 문제가 있다고 생각되는데요,

아니면 type을 long long으로 해야될 어느 부분인가가 int로 되어있거나.. ㅠ


문제설명:

메테오가 떨어져요.

l,r,a 형식으로 주어지고 l<=r이면 l~r구간에 돌댕이가 a개 떨어져요.

l>r이면 1~r, l~(총 섹터 수) 구간에 돌댕이가 a개 떨어져요. (여기 떨어지는 섹터가 원궤도라서 구간이 저래요..)

근데 회원국이 섹터들을 띄엄띄엄 가지고 있는 형태에요. 물론 붙어있을 수도 있구요. 그리고 각 나라별로 목표한 돌댕이 수가 있어서 그걸 몇일만에 다 채웠냐~ 하는걸 출력하는게 문제에요.

쿼리제한과 섹터 수, 회원국 수는 모두 30만이에요.


변수 설명을 하자면,

sect: 회원국이 소유하고 있는 섹터를 의미합니다. sect[i]=x; => i번째 회원국은 x라는 섹터를 가지고 있다는 뜻.

goal: 각 회원국이 챙겨야할 돌댕이 샘플 수를 의미합니다. (goal[i]=x; => i번째 회원국이 목표로 하는 돌댕이 수)

cp[day]={x1,x2,x3,x4,x5,...} 이런식으로 들어가게 되는데, complete의 약자로 쓴거구요 day번째 날에 샘플을 다 모을 가능성이 있는 나라들이 x1, x2, x3,... 다~ 라는 식으로 들어갑니다.

day[i]: i번째날 메테오가 어떤 구간에 떨어지는지 저장하고 있습니다.


개인적으로는 98번째줄이 가장 의심이 갑니다.. r[i]!=q+1말고 다른 케이스가 있을수도 있을것 같아서요


도와주시면 감사하겠습니다~!



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