记录编号	432998	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	1.392 s
提交时间	2017-08-04 15:12:06	内存使用	96.45 MiB

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
int n,m,w[MAXN],v[MAXN],cnt,root[MAXN],sz,Hash[MAXN];
ll s,sum,val,Ans;
#define fastcall __attribute__((optimize("-O3")))
#define IL __inline__ __attribute__((always_inline)) 
  
  
template<typename _t>
fastcall IL _t read(){
    register _t x=0,f=1;
    register char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-f;
    for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
    return x*f;
}
  
struct qujian{
    int l,r;
}a[MAXN];
  
struct node{
    int l,r;
    ll val,sum;
}tree[MAXN*20];
  
#define l(x) tree[x].l
#define r(x) tree[x].r
#define s(x) tree[x].sum
#define v(x) tree[x].val
  
fastcall inline void insert(int &o,int old,int l,int r,int pos,int val){
    o=++cnt;
    tree[o]=tree[old];
    s(o)++;v(o)+=val;
    if(l==r)return;
    int m = l+r>>1;
    if(pos<=m)insert(l(o),l(old),l,m,pos,val);
    else insert(r(o),r(old),m+1,r,pos,val);
}
  
fastcall inline void Query(int old,int now,int l,int r,int x,int y){
    if(x>y)return;
    if(x<=l&&r<=y){
        sum+=s(now)-s(old);//勿忘清空
        val+=v(now)-v(old);
        return;
    }
    int m = l+r>>1;
    if(x<=m)Query(l(old),l(now),l,m,x,y);
    if(m<y)Query(r(old),r(now),m+1,r,x,y);
}
  
fastcall inline void build(int &o,int l,int r){
    o=++cnt;
    s(o)=v(o)=0;
    if(l==r)return;
    int m=l+r>>1;
    build(l(o),l,m);
    build(r(o),m+1,r);
}
fastcall IL int GHash(ll x){return std :: lower_bound(&Hash[1],&Hash[sz+1],x)-Hash;}
  
fastcall IL ll calc(register int mid){
    register ll ans=0;
    for(register int i=1;i<=m;i++){
        sum=0;val=0;
        Query(root[a[i].l-1],root[a[i].r],1,sz,mid,sz);
        ans += (ll)sum*val;
    }
    return ans;
}
  
int main(){
    freopen("qc.in","r",stdin);
    freopen("qc.out","w",stdout);    
    n=read<int>();m=read<int>();s=read<ll>();
    for(int i=1;i<=n;i++)w[i]=read<int>(),Hash[i]=w[i],v[i]=read<int>();
    std::sort(Hash+1,Hash+1+n);
    sz = std::unique(Hash+1,Hash+1+n)-Hash-1;
    build(root[0],1,n);
    for(register int i=1;i<=n;i++)insert(root[i],root[i-1],1,sz,GHash(w[i]),v[i]);
    for(register int i=1;i<=m;i++)a[i].l=read<int>(),a[i].r=read<int>();
    int L=1,R=sz;Ans=0x3f3f3f3f3f3f3f3fll;
    while(L<=R){
        int mid = L+R>>1;
        ll ans=calc(mid);
        if(ans>s)L=mid+1;
        else R=mid-1;
        Ans=min(Ans,abs(ans-s));
    }
    printf("%lld\n",Ans);
}