0pts球调qwq

Tachibana27 @ 2023-09-22 09:37:58

#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int s=0;

    int w=1;

    char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())

        if(ch=='-')

            w=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())

        s=s*10+ch-'0';

    return s*w;

}

void write(int x) {

    if(x<0){

        putchar('-');

        x=-x;

    }

    if(x>9)

        write(x/10);

    putchar(x%10+'0');

    return;

}

int n,m,s;

int ans=1145141919;

struct node{

    int w;

    int v;

}a[200086];

int l[200086];

int r[200086];

int sum1[200086];

int sum2[200086];

void ssum(int W){

    if(a[1].w>=W){

        sum1[1]=1;

        sum2[1]=a[1].v;

    }

    for(int i=2;i<=n;i++)

        if(a[i].w>=W){

            sum1[i]=sum1[i-1]+1;

            sum2[i]=sum2[i-1]+a[i].v;

        }

        else{

            sum1[i]=sum1[i-1];

            sum2[i]=sum2[i-1];

        }

}//前缀和 

int f(int W){

    ssum(W);

    int sum=0;

    for(int i=1;i<=m;i++)

        sum+=(sum1[r[i]]-sum1[l[i]-1])*(sum2[r[i]]-sum2[l[i]-1]);

//  cout<<sum<<"\n\n";

    return sum;

}//同check函数 

int main(){

    n=read();

    m=read();

    s=read();

    for(int i=1;i<=n;i++){

        a[i].w=read();

        a[i].v=read();

    }

    for(int i=1;i<=m;i++){

        l[i]=read();

        r[i]=read(); 

    }

    int ll=1;

    int rr=n;

    int mid=0;  

    while(ll<=rr){

        mid=(ll+rr)/2;

        ans=min(ans,abs(f(mid)-s));//去最接近的值 

        if(f(mid)>s)

            ll=mid+1;

        else

            rr=mid-1;

//      cout<<mid<<"    "<<ans<<"\n\n";

    }//二分 

//  }

//  cout<<mid<<"    "<<ans<<"\n\n";

    write(ans);

    return 0;

}

by Tachibana27 @ 2023-09-22 09:50:35

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){

    int s=0;

    int w=1;

    char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())

        if(ch=='-')

            w=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())

        s=s*10+ch-'0';

    return s*w;

}

void write(int x) {

    if(x<0){

        putchar('-');

        x=-x;

    }

    if(x>9)

        write(x/10);

    putchar(x%10+'0');

    return;

}

int n,m,s;

int ans=1145141919;

struct node{

    int w;

    int v;

}a[200086];

int l[200086];

int r[200086];

int sum1[200086];

int sum2[200086];

void ssum(int W){

    if(a[1].w>=W){

        sum1[1]=1;

        sum2[1]=a[1].v;

    }

    for(int i=2;i<=n;i++)

        if(a[i].w>=W){

            sum1[i]=sum1[i-1]+1;

            sum2[i]=sum2[i-1]+a[i].v;

        }

        else{

            sum1[i]=sum1[i-1];

            sum2[i]=sum2[i-1];

        }

}//前缀和 

int f(int W){

    ssum(W);

    int sum=0;

    for(int i=1;i<=m;i++)

        sum+=(sum1[r[i]]-sum1[l[i]-1])*(sum2[r[i]]-sum2[l[i]-1]);

//  cout<<sum<<"\n\n";

    return sum;

}//同check函数 

signed main(){

    n=read();

    m=read();

    s=read();

    for(int i=1;i<=n;i++){

        a[i].w=read();

        a[i].v=read();

    }

    for(int i=1;i<=m;i++){

        l[i]=read();

        r[i]=read(); 

    }

    int ll=1;

    int rr=1e18;

    int mid=0;  

    while(ll<=rr){

        mid=(ll+rr)/2;

        ans=min(ans,abs(f(mid)-s));//去最接近的值 

        if(f(mid)>s)

            ll=mid+1;

        else

            rr=mid-1;

//      cout<<mid<<"    "<<ans<<"\n\n";

    }//二分 

//  }

//  cout<<mid<<"    "<<ans<<"\n\n";

    write(ans);

    return 0;

}

粘份新代码

by Tachibana27 @ 2023-09-22 10:13:44

已过，ctj