fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 5e4 + 5;
  5. const long long INF = 1e18;
  6.  
  7. long long a[MaxN];
  8. long long st[4*1005];
  9.  
  10. long long n,m,ans=0;
  11.  
  12. void update(long long id,long long l,long long r,long long pos,long long val)
  13. {
  14.     if(l==r)
  15.     {
  16.         st[id]=min(st[id],val);
  17.         return;
  18.     }
  19.  
  20.     long long mid=(l+r)/2;
  21.  
  22.     if(pos<=mid)
  23.     {
  24.         update(id*2,l,mid,pos,val);
  25.     }
  26.     else
  27.     {
  28.         update(id*2+1,mid+1,r,pos,val);
  29.     }
  30.  
  31.     st[id]=min(st[id*2],st[id*2+1]);
  32. }
  33.  
  34. long long get(long long id,long long l,long long r,long long u,long long v)
  35. {
  36.     if(v<l || r<u)
  37.     {
  38.         return INF;
  39.     }
  40.  
  41.     if(u<=l && r<=v)
  42.     {
  43.         return st[id];
  44.     }
  45.  
  46.     long long mid=(l+r)/2;
  47.  
  48.     return min(get(id*2,l,mid,u,v),
  49.                get(id*2+1,mid+1,r,u,v));
  50. }
  51.  
  52. int main()
  53. {
  54.     ios_base::sync_with_stdio(0);
  55.     cin.tie(0);
  56.  
  57.     if(fopen("airc.inp","r"))
  58.     {
  59.         freopen("airc.inp","r",stdin);
  60.         freopen("airc.out","w",stdout);
  61.     }
  62.  
  63.     cin >> n;
  64.  
  65.     for(long long i=1;i<=n;i++)
  66.     {
  67.         cin >> a[i];
  68.     }
  69.  
  70.     cin >> m;
  71.  
  72.     for(long long i=1;i<=4*1000;i++)
  73.     {
  74.         st[i]=INF;
  75.     }
  76.  
  77.     for(long long i=1;i<=m;i++)
  78.     {
  79.         long long b,c;
  80.         cin >> b >> c;
  81.         update(1,1,1000,b,c);
  82.     }
  83.  
  84.     for(long long i=1;i<=n;i++)
  85.     {
  86.         ans+=get(1,1,1000,a[i],1000);
  87.     }
  88.  
  89.     cout << ans;
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ud1Zek
language:
C++14 (gcc 8.3)
created:
22 hours 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!