fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. #define x first 
  4. #define y second 
  5.  
  6. #define siz(v) ((int)(v).size()) 
  7. #define all(v) begin((v)), end(v) 
  8. #define filter(v) sort(all(v)); v.resize(unique(all(v)) - begin(v)) 
  9.  
  10. #define BIT(x, i) (((x) >> (i)) & 1) 
  11. #define MASK(i) (1LL << (i)) 
  12.  
  13. #define dbg(x) "[" #x " = " << x << "]" 
  14.  
  15. using namespace std; 
  16.  
  17. typedef pair<int, int > ii; 
  18. typedef pair<long long, int > lli; 
  19.  
  20. bool M1; 
  21. const int infINT = 1e9 + 123; 
  22. const long long inf = 1e18 + 12; 
  23. const int mod = 1000000007; 
  24.  
  25. const int dx[4] = {-1, 0, 0, 1}; 
  26. const int dy[4] = {0, -1, 1, 0}; 
  27.  
  28. template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;} 
  29. template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;} 
  30.  
  31. void add(int &a, const int &b){ 
  32.     a += b; 
  33.     if (a >= mod) a -= mod; 
  34. } 
  35.  
  36. int bin_pow(int a, int k){ 
  37.     int res = 1; 
  38.     while(k){ 
  39.         if (k & 1) res = 1LL * res * 1LL * a % mod; 
  40.         k >>= 1; a = 1LL * a * 1LL * a % mod; 
  41.     } 
  42.     return res; 
  43. } 
  44.  
  45. const int MAXK = 2e5 + 5; 
  46.  
  47. long long X, Y, numTree, res[MAXK]; 
  48. pair<long long, long long> tree[MAXK]; 
  49. vector<int > pos; 
  50. vector<long long > comp; 
  51.  
  52. struct segmentTree{ 
  53.     int n; 
  54.     vector<long long > mx; 
  55.  
  56.     segmentTree(int _n = 0): n(_n){ 
  57.         mx.assign(n << 2 | 1, 0); 
  58.     } 
  59.  
  60.     void update(int id, int l, int r, int u, int v, long long x){ 
  61.         if (l > r || l > v || r < u || u > v) return; 
  62.         if (l >= u && r <= v) return mx[id] = max(mx[id], x), void(); 
  63.         int m = (l + r) >> 1; 
  64.         update(id << 1, l, m, u, v, x); 
  65.         update(id << 1 | 1, m + 1, r, u, v, x); 
  66.     } 
  67.  
  68.     void update(int u, int v, long long x){ 
  69.         update(1, 1, n, u, v, x); 
  70.     } 
  71.  
  72.     long long get(int id, int l, int r, int p){ 
  73.         if (l == r) return mx[id]; 
  74.         int m = (l + r) >> 1; 
  75.         if (p <= m) return max(mx[id], get(id << 1, l, m, p)); 
  76.         else return max(mx[id], get(id << 1 | 1, m + 1, r, p)); 
  77.     } 
  78.  
  79.     long long get(int p){ 
  80.         return get(1, 1, n, p); 
  81.     } 
  82. }; 
  83.  
  84. void input(){ 
  85.     cin >> X >> Y >> numTree; 
  86.  
  87.     for(int i = 1; i <= numTree; i++){ 
  88.         double x, y; cin >> x >> y; 
  89.         tree[i].x = round(x * 2); 
  90.         tree[i].y = round(y * 2); 
  91.         comp.push_back(tree[i].y); 
  92.         pos.push_back(i); 
  93.     } 
  94. } 
  95.  
  96. long long getPos(const long long &pos) { 
  97.     return lower_bound(all(comp), pos) - begin(comp) + 1; 
  98. } 
  99.  
  100. bool cmp(const int &a, const int &b){ 
  101.     return tree[a] < tree[b]; 
  102. } 
  103.  
  104. void solve(){ 
  105.     filter(comp); 
  106.     sort(all(pos), cmp); 
  107.  
  108.     segmentTree it(siz(comp)); 
  109.  
  110.     for(int i: pos) { 
  111.         long long len = tree[i].x - it.get(getPos(tree[i].y)); 
  112.         int L = lower_bound(all(comp), tree[i].y - len) - begin(comp) + 1; 
  113.         int R = upper_bound(all(comp), tree[i].y + len) - begin(comp); 
  114.         res[i] = len; 
  115.         it.update(L, R, tree[i].x + len); 
  116.     } 
  117.  
  118.     for(int i = 1; i <= numTree; i++) 
  119.         cout << res[i] << '\n'; 
  120. } 
  121.  
  122. bool M2; 
  123. int main(){ 
  124.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  125.     #define task "test" 
  126.     if (fopen(task".inp", "r")){ 
  127.         freopen(task".inp", "r", stdin); 
  128.         freopen(task".out", "w", stdout); 
  129.     } 
  130.     int t = 1; 
  131. //    cin >> t; 
  132.     while(t--){ 
  133.         input(); 
  134.         solve(); 
  135.     } 
  136.     cerr << (1.0  * clock()) / CLOCKS_PER_SEC << ".s\n"; 
  137.     cerr << (&M2 - &M1) / 1048576 << " mb\n"; 
  138. } 
  139.  
  140.  
Success #stdin #stdout #stderr 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
0.003995.s
-4 mb
https://ideone.com/uQ0Ndo
language:
C++14 (gcc 8.3)
created:
3 days 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!