diltraser @ 2018-08-28 14:20:41
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int M=0;
int sum[200010];
int num[200010];
int w[200010];
int v[200010];
int left[200010];
int right[200010];
int n,m;
ll s;
void find(int x){
int i;
for(i=1;i<=n;i++){
num[i]=num[i-1];
sum[i]=sum[i-1];
if(w[i]>=x){
num[i]++;
sum[i]+=v[i];
}
}
}
ll check(int x){
int i;
find(x);
ll ans=0;
for(i=1;i<=m;i++)
ans+=(num[right[i]]-num[left[i]-1])
*(sum[right[i]]-sum[left[i]-1]);
return llabs(s-ans);
}
ll search(int minn,int maxn){
ll ans=0;
while(maxn-minn>1){
int mid=minn+(maxn-minn)/2;
find(mid);
ans=0;
int i;
for(i=1;i<=m;i++)
ans+=(num[right[i]]-num[left[i]-1])
*(sum[right[i]]-sum[left[i]-1]);
if(ans<s)
maxn=mid;
if(ans==s)return 0;
if(ans>s)minn=mid;
}
return min(check(maxn),check(minn));
}
int main(){
scanf("%d%d%lld",&n,&m,&s);
int i;
for(i=1;i<=n;i++){
scanf("%d%d",&w[i],&v[i]);
M=max(M,w[i]);
}
for(i=1;i<=m;i++)
scanf("%d%d",&left[i],&right[i]);
printf("%lld",search(1,M));
return 0;
}by 我没有小白 @ 2018-10-09 21:51:32
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define LL long long
using namespace std;
const int N = 200010;
int n,q,w[N],v[N],l=2000005,r,L[N],R[N];
LL sumw[N],sumv[N];
LL s,minn=9999999999999999ll;
LL _abs(LL x) {
return x>0?x:-x;
}
LL min(LL x,LL y) {
return x<y?x:y;
}
LL max(LL x,LL y){
return x>y?x:y;
}
bool judge(int mid) {
memset(sumw,0,sizeof(sumw));
memset(sumv,0,sizeof(sumv));
for(int i=1; i<=n; i++) {
if(w[i]>=mid) sumw[i]=sumw[i-1]+1,sumv[i]=sumv[i-1]+v[i];
else sumw[i]=sumw[i-1],sumv[i]=sumv[i-1];
}
LL ans=0;
for(int i=1; i<=q; i++) {
ans+=(sumw[R[i]]-sumw[L[i]-1])*(sumv[R[i]]-sumv[L[i]-1]);
}
minn=min(minn,_abs(ans-s));
if(ans>s)return true;
else return false;
}
int main() {
// freopen("a.in","r",stdin);
scanf("%d%d%lld",&n,&q,&s);
for(int i=1; i<=n; i++) scanf("%d%d",&w[i],&v[i]),l=min(l,w[i]),r=max(r,w[i]);
for(int i=1; i<=q; i++) scanf("%d%d",&L[i],&R[i]);
while(l<=r) {
int m=(l+r)>>1;
if(judge(m)) l=m+1;
else r=m-1;
}
printf("%lld",minn);
}90同求
by 迦娜酱 @ 2018-10-12 16:13:14
#include<bits/stdc++.h>
using namespace std;
int sumg[300000];
int sumv[300000];
int va[300000];
int w[300000];
int mxva;
unsigned long long S;
int n , m;
int miva = 500000;
unsigned long long ans = 7878797000979087987;
struct qus{
int l , r;
}qs[300000];
inline void get_sfx( int lim ){
for( register int i = 1 ; i <= n ; ++i ){
sumg[i] = sumg[i - 1];
sumv[i] = sumv[i - 1];
if( w[i] >= lim ){
++sumg[i];
sumv[i] += va[i];
}
}
}
inline long long check( int lim ){
get_sfx( lim );
unsigned long long quk = 0;
for( register int i = 1; i <= m ; ++i ){
long long pl = sumg[qs[i].r] - sumg[qs[i].l - 1];
long long lp = sumv[qs[i].r] - sumv[qs[i].l - 1];
quk += pl * lp;
}
return quk;
}
void merge( ){
while( mxva > miva ){
int mid = (mxva + miva)>>1;
unsigned long long temp = check( mid );
if( temp > S ) miva = mid + 1;
else if( temp == S ) {ans = 0;return;}
else mxva = mid;
unsigned long long ttemp = max( S , temp ) - min( S , temp );
ans = min( ans , ttemp );
}
}
int main(){
scanf( "%d%d%lld" ,&n ,&m ,&S );
for( register int i = 1; i <= n ; ++i ){
scanf( "%d%d" , &w[i] ,&va[i] );
miva = min( w[i] , miva );
mxva = max( w[i] , mxva );
}
for( register int i = 1; i <= m ; ++ i ){
scanf( "%d%d" ,&qs[i].l ,&qs[i].r );
}
merge();
cout<<ans;
}
/*
10 10 1475400
23954 25180
18805 2701
17195 5663
7044 13659
8139 30927
19774 25516
7472 4572
5999 6166
1185 13621
10414 26521
2 10
4 7
5 8
1 6
2 7
1 3
2 7
3 4
1 6
1 10
*/MMP就我一个95求吗qwq
by 迦娜酱 @ 2018-10-12 16:58:24
明白叻qwq
左右端点不能直接赋成Wi的最大最小值
而是要比Wi的最大值大一点
比Wi的最小值小一点
qwqwqwqwqwqwqwqwq