fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17.  
  18. const int MAX=3e5+5,maxCord=1e6+6;
  19. int n,m;
  20. ll fw[maxCord],res[MAX];
  21. struct Event
  22. {
  23.     int pos,type,val,idx;
  24.     ll weight;
  25.     bool operator <(const Event &other) const 
  26.     {
  27.         return (pos<other.pos) || (pos==other.pos && type<other.type);
  28.     }
  29. };
  30. vector<Event> event;
  31. void update(int pos, ll val)
  32. {
  33.     for(;pos<maxCord;pos+=(pos&(-pos))) fw[pos]+=val;
  34. }
  35. ll query(int pos)
  36. {
  37.     ll ans=0;
  38.     for(;pos>=1;pos-=(pos&(-pos))) ans+=fw[pos];
  39.     return ans;
  40. }
  41.  
  42. void calc()
  43. {
  44.     sort(event.begin(),event.end());
  45.     foru(i,0,event.size()-1)
  46.     {
  47.         Event e=event[i];
  48.         if(e.type==0) update(e.val,e.weight);
  49.         else 
  50.         {
  51.             res[e.idx]=query(1000000)-query(e.val-1);
  52.         }
  53.     }
  54.     foru(i,1,m) cout<<res[i]<<el;
  55. }
  56.  
  57. int main()
  58. {
  59.     fastio
  60.     if(fopen(FILE ".inp","r"))
  61.     {
  62.         freopen(FILE ".inp","r",stdin);
  63.         freopen(FILE ".out","w",stdout);
  64.     }
  65.  
  66.     cin>>n;
  67.     foru(i,1,n)
  68.     {
  69.         int l,r; ll c; cin>>l>>r>>c;
  70.         event.pb({l,0,r,0,c});
  71.     }
  72.     cin>>m;
  73.     foru(i,1,m)
  74.     {
  75.         int s,t; cin>>s>>t;
  76.         event.pb({t,1,s,i,0});
  77.     }
  78.     calc();
  79.  
  80.     return 0;
  81. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zVB9Ik
language:
C++14 (gcc 8.3)
created:
21 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!