1112. - 저도 B 아니에요.

DESCRIPTION
작은 L 은 QQ 개수 가 한 줄 로 되 어 있 고 왼쪽 에서 오른쪽으로 A1A 1 부터 AQAQAQ 까지 이 숫자 를 좋아 합 니 다.
어느 날, L 군 이 수 능 에 지원 하 러 갔 어 요. J 군 과 N 군 이 와 서 이 숫자 로 게임 을 했 어 요.
처음에 작은 N 손 에 빈 시퀀스 가 있 었 습 니 다. 변 수 를 정의 합 니 다. C: = 0 C: = 0.작은 J 는 왼쪽 에서 오른쪽으로 순서대로 서열 중의 수 를 꺼 내 작은 N 의 손 서열 의 맨 오른쪽 에 놓 고 놓 은 후에 전체 서열 의 혼란 도가 MM 을 초과 하면 작은 N 은 손 에 있 는 모든 수 를 모두 버 리 고 C: = C + 1C: = C + 1 을 명령 합 니 다.
길 이 를 KK 서열 로 정의 하 는 혼란 도 S = K ∑ i = 1bi×ViS=∑i=1KBi×Vi, 그 중에서 Bi 는 서열 중의 ii 작은 수 를 나타 내 고 VV 는 주어진 서열 이다.
작은 J 와 작은 N 은 각 수 를 넣 으 면 CC 가 얼마 인지 알 고 싶 어 합 니 다.
INPUT
첫 줄 두 정수
QQ，
MM 다음 줄.
QQ 개 정수, 제
ii 개 정수 표시
아이 야, 다음 줄.
QQ 개 정수, 제
ii 개 정수 표시
ViVi
OUTPUT
한 줄
QQ 개 정수, 제
ii 개 정수 가입 제 표시
ii 개수 다음
CC, 인접 한 두 정수 사 이 를 빈 칸 으로 구분 합 니 다. 마지막 숫자 후 빈 칸 출력 이 끝나 지 않도록 줄 을 바 꾸 십시오.
SAMPLE INPUT
5 11 3 2 5 41 1 1 1 1
SAMPLE OUTPUT
0 1 2 3 4
HINT
1 ≤ Q ≤ 300000, 0 ≤ M ≤ 1018, 1 ≤ Ai ≤ 108, 1 ≤ Vi ≤ 1041 ≤ Q ≤ 300000, 0 ≤ M ≤ 1018, 1 ≤ Ai ≤ 108, 1 ≤ Vi ≤ 104 모든 것 에 대한
1≤i≤Q−1,Vi≤Vi+11≤i≤Q−1,Vi≤Vi+1
SOLUTION
"영롱 한 컵" ACM 경기 라운드 \ # 13
B
한 가지 분명 한 생각 은 매번 2 분 에 몇 번 째 숫자 에 가입 할 때마다 혼란 도가 MM 을 초과 한 다음 에 폭력 검 사 를 하 는 것 이다. 복잡 도 는 O (N2logN) O (N2logN) 등급 일 수 있다.
우 리 는 2 분 방식 을 바 꿀 수 있다.
현재 왼쪽 끝 점 을 LL 로 합 니 다. 우 리 는 먼저 가장 작은 KK 를 찾 아서 [L, L + 2K) [L, L + 2K) 이 구간 의 혼란 도가 MM 을 초과 하도록 합 니 다.
그리고 오른쪽 끝 점 은 [L + 2K - 1, L + 2K) [L + 2K - 1, L + 2K) 에서 2 분 이면 됩 니 다.
최소 2K - 12K - 1 개 수 를 삭제 할 때마다 필요 한 시간 복잡 도 는 O (2KKlogn) O (2KKlogn) 이다.
그러므로 전체 복잡 도 는 O (NLog2N) 이다.
처음에 생각 했 을 때 M 이 크 면 C 가 적 게 늘 어 나 고 중간 에 계산 한 것 이 많 지 않 으 며 M 이 작 으 면 정렬 한 숫자 가 작다 고 생각 했 어 요. 아무리 생각해 도 모 르 겠 어 요. 2 점, 2 점. 클래식 해 요.

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=300000;
int ans[300005];
ll a[300005];
ll v[300005];
ll tmp[300005];
int p[29];
void init()
{
    p[0]=1;
    for(int i=1; i<=25; i++)
        p[i]=p[i-1]*2;
}
int judge(int l,int r,ll m)
{
    ll sum=0;
    int cnt=0;
    for(int i=l; i<=r; i++)
        tmp[cnt++]=a[i];
    sort(tmp,tmp+cnt);
    for(int i=0;im)
        return 1;
    return 0;
}
int g(int l,int r1,int r2,ll m)
{
    while(r1>1;
        if(judge(l,midr,m))
            r2=midr;
        else
            r1=midr+1;
    }
    return r1;
}
int check(int l,int n,ll m)
{
    int r1=l;
    int r2=l;
    for(int i=0;; i++,r2+=p[i])
    {
        if(r2>n)
            r2=n;
        if(judge(l,r2,m))
            break;
        r1=r2+1;
        if(r2==n)
            break;
    }
    return g(l,r1,r2,m);
}
void f(int n,ll m)
{
    int i=0;
    while(i