求助大牛 30分没找到错误在哪里
查看原帖
求助大牛 30分没找到错误在哪里
1149836
thesadbee楼主2024/4/19 09:06

代码如下,求助各位大牛

#include<bits/stdc++.h>
#define ll long long
#define ri register int
using namespace std;
const int MAXN=1e5+10;
int n,q,d[MAXN],c[MAXN],r,v,b[MAXN],nxt[MAXN][20],sum[MAXN][20];
stack <int> stk;

void fisrt(){
    for(int i=1;i<=n;i++){
        while(!stk.empty()&&d[i]>d[stk.top()]){
            nxt[stk.top()][0]=i;
            sum[stk.top()][0]=c[i];
            stk.pop();
    }
    stk.push(i);
    }
    while(!stk.empty()){
        nxt[stk.top()][0]=0;
        stk.pop();
    }
}

void putin(){
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)<=n;i++){
            nxt[i][j]=nxt[nxt[i][j-1]][j-1];
            sum[i][j]=sum[i][j-1]+sum[nxt[i][j-1]][j-1];
        }
    }
}

int quest(int x,int y){
    if(c[x]>=y) return x;
    y-=c[x];
    for(int i=18;i>=0;i--){
        if(nxt[r][i]!=0&&y>sum[x][i]){
            y-=sum[x][i];
            x=nxt[x][i];
        }
    }
    return nxt[x][0];
}

int main(){
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&d[i],&c[i]);
    }
    memset(sum,0x3f,sizeof(sum));
    fisrt();
    putin();
    for(int i=1;i<=q;i++){
        scanf("%d %d",&r,&v);
        printf("%d\n",quest(r,v));
    }
}
2024/4/19 09:06
加载中...