fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("avx,avx2,fma")
  3. #pragma GCC target ("avx2")
  4. #pragma GCC optimization ("O3")
  5. #pragma GCC optimization ("unroll-loops")
  6. #include <bits/stdc++.h>
  7. #define i64 long long
  8. #define int long long
  9. #define fi first
  10. #define se second
  11. #define all(v) v.begin(),v.end()
  12. #define pb push_back
  13. //#define mp make_pair
  14. #define lwb lower_bound
  15. #define upb upper_bound
  16. #define endl '\n'
  17.  
  18. using namespace std;
  19.  
  20. typedef pair<int,int> ii;
  21. typedef vector<int> veci;
  22.  
  23. const int inf=1e9;
  24. const i64 Inf=1e18;
  25. const int base=10;
  26. const int mod=1e9+7;
  27. const int N=1e5+5;
  28. const int K=(1<<10)+5;
  29.  
  30. int n,m;
  31. int bit[N],f[N][22],ans[N];
  32. struct ds{
  33.     int p,kid;
  34. }a[N];
  35. struct query{
  36.     int b,p,pos;
  37. }q[N];
  38.  
  39. void upd(int u,int val){
  40.     for(;u<=n;u+=(u&(-u))) bit[u]+=val;
  41. }
  42.  
  43. int get(int u){
  44.     int ans=0;
  45.     for(;u>0;u-=(u&(-u))) ans+=bit[u];
  46.     return ans;
  47. }
  48.  
  49. int get_min(int i,int j){
  50.     int k=log2(j-i+1);
  51.     return min(f[i][k],f[j-(1<<k)+1][k]);
  52. }
  53.  
  54. void create(){
  55.     for(int i=1;i<=n;i++){
  56.         upd(i,a[i].p);
  57.         upd(i+1,-a[i].p);
  58.     }
  59.     for(int i=1;i<=n;i++) f[i][0]=a[i].kid;
  60.     int mk=log2(n)+1;
  61.     for(int k=1;k<=mk;k++)
  62.         for(int i=1;i+(1<<k)-1<=n;i++)
  63.             f[i][k]=min(f[i][k-1],f[i+(1<<(k-1))][k-1]);
  64. }
  65.  
  66. int tknp_left(int l,int r,int x){
  67.     int vt=-1;
  68.     while(l<=r){
  69.         int m=(l+r)/2;
  70.         int pos=get(m);
  71.         if(pos<=x) {vt=m; l=m+1;}
  72.         else r=m-1;
  73.     }
  74.     return vt;
  75. }
  76. int tknp_right(int l,int r,int x){
  77.     int vt=-1;
  78.     while(l<=r){
  79.         int m=(l+r)/2;
  80.         int pos=get(m);
  81.         if(pos>x) {vt=m; r=m-1;}
  82.         else l=m+1;
  83.     }
  84.     return vt;
  85. }
  86. int find_left(int l,int r,int x){
  87.     int vt=-1;
  88.     while(l<=r){
  89.         int m=(l+r)/2;
  90.         int pos=get(m);
  91.         if(pos==x) {vt=m; r=m-1;};
  92.         if(pos<x) l=m+1;
  93.         if(pos>x) r=m-1;
  94.     }
  95.     return vt;
  96. }
  97. int find_right(int l,int r,int x){
  98.     int vt=-1;
  99.     while(l<=r){
  100.         int m=(l+r)/2,pos=get(m);
  101.         if(pos==x) {vt=m; l=m+1;}
  102.         if(pos<x) l=m+1;
  103.         if(pos>x) r=m-1;
  104.     }
  105.     return vt;
  106. }
  107.  
  108. void input(){
  109.     cin>>n;
  110.     for(int i=1;i<=n;i++){
  111.        cin>>a[i].p;
  112.        a[i].kid=i;
  113.     }
  114.     sort(a+1,a+n+1,[&](const ds &x,const ds&y){
  115.              return x.p<y.p;
  116.          });
  117.     cin>>m;
  118.     for(int i=1;i<=m;i++) cin>>q[i].b>>q[i].p,q[i].pos=i;
  119.     sort(q+1,q+m+1,[&](const query &x,const query &y){
  120.              return x.b>y.b;
  121.          });
  122.     create();
  123. }
  124.  
  125. void progress(){
  126.     for(int i=1;i<=m;i++){
  127.         int vt1=tknp_left(1,n,q[i].p);
  128.         int vt2=tknp_right(1,n,q[i].p);
  129.         int d1=Inf,d2=Inf,dist=Inf;
  130.         if(vt1!=-1) d1=abs(get(vt1)-q[i].p);
  131.         if(vt2!=-1) d2=abs(get(vt2)-q[i].p);
  132.         if(d1<d2){
  133.             int vt=find_left(1,n,get(vt1));
  134.             ans[q[i].pos]=get_min(vt,vt1);
  135.         }
  136.         if(d1>d2){
  137.             int vt=find_right(1,n,get(vt2));
  138.             ans[q[i].pos]=get_min(vt2,vt);
  139.         }
  140.         if(d1==d2){
  141.             int l=find_left(1,n,get(vt1));
  142.             int r=find_right(1,n,get(vt2));
  143.             ans[q[i].pos]=get_min(l,r);
  144.         }
  145.         dist=min(d1,d2);
  146.         if(vt1!=-1) upd(1,dist),upd(vt1+1,-dist);
  147.         if(vt2!=-1) upd(vt2,-dist);
  148.     }
  149.     for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
  150. }
  151.  
  152. signed main(){
  153.     ios_base::sync_with_stdio(0);
  154.     cin.tie(0);cout.tie(0);
  155.  
  156.     #define FILE "mttd"
  157.     if(fopen(FILE".inp","r")){
  158.         freopen(FILE".inp","r",stdin);
  159.         freopen(FILE".out","w",stdout);
  160.     }
  161.  
  162.     int test=1;
  163. //    cin>>test;
  164.     while(test--){
  165.         input();
  166.         progress();
  167.     }
  168. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bxLbdK
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!