daily pastebin goal
39%
SHARE
TWEET

Untitled

a guest May 16th, 2018 100 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 2*1000*100+7;
  4. int S[N];
  5. int T[N];
  6. int t[4*N];
  7. void update(int v,int s,int e,int l,int r,int val){
  8.     if(l>r) return;
  9.     if(s == l && e == r) {
  10.         t[v] = val;
  11.         return;
  12.     }
  13.     int m = (s+e)/2;
  14.     update(v*2,s,m,l,min(m,r),val);
  15.     update(v*2+1,m+1,e,max(l,m+1),r,val);
  16.     t[v] = t[v*2]+t[v*2+1];
  17. }
  18. int query(int v,int s,int e,int l,int r){
  19.     if(l>r) return 0;
  20.     if(s == l && e == r) return t[v];
  21.     int m = (s+e)/2;
  22.     return query(v*2,s,m,l,min(m,r)) + query(v*2+1,m+1,e,max(l,m+1),r);
  23. }
  24. int main()
  25. {
  26. //    freopen("boarding.in","r",stdin);
  27. //    freopen("boarding.out","w",stdout);
  28.     int n;
  29.     scanf("%d",&n);
  30.     for(int i = 1;i<=n;i++) scanf("%d%d",&S[i],&T[i]);
  31.     int ans = 0;
  32.     for(int i = n;i>=1;i--){
  33.         update(1,1,n,S[i],S[i],T[i]);
  34.         int x = query(1,1,n,1,S[i]);
  35.         x+=(S[i]+(n-i));
  36.         ans = max(ans,x);
  37.     }
  38.     printf("%d\n",ans);
  39.  
  40.     return 0;
  41. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top