fork(2) download 
  1. /*
  2.  *  Author: Tara Prasad
  3.  *  Problem: POSTERS
  4.  */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. #define F first
  9. #define S second
  10. #define mp make_pair
  11. #define mt make_tuple
  12. #define pb push_back
  13. #define ALL(x) x.begin(), x.end()
  14. #define REV_ALL(x) x.rbegin(), x.rend()
  15. #define SZ(x) (int)x.size()
  16. #define CONTAINS(cont, val) (cont.find(val) != cont.end())
  17. #define endl '\n'
  18. #define what_is(x) cout << #x << " = " << x << endl
  19. #define IO_SPEED_UP ios::sync_with_stdio(false);cin.tie(NULL)
  20. #define FOR(i, st, ed, inc) for(ll i = st; i < ed; i += inc)
  21. #define leftmost_set(x) __builtin_clzll(x)
  22.  
  23. typedef long long ll;typedef pair<ll, ll> ii;
  24. typedef vector<ll> vi;typedef vector<bool> vb;
  25. typedef vector<ii> vii;typedef vector<vi> vvi;
  26.  
  27. const ll PINF = 1E9;
  28. const ll NINF = -1E9;
  29. const ll M = 1E9 + 7;
  30. const double EPS = 1E-9;
  31. const int N = 40005;
  32.  
  33. int n;
  34. vi lazy;
  35.  
  36. void shift(int id) {
  37.   if(lazy[id]) 
  38.     lazy[2 * id] = lazy[2 * id + 1] = lazy[id];
  39.   lazy[id] = 0;
  40. }
  41.  
  42. void paint(int x, int y, int color, int id = 1, int l = 0,int r = n){
  43.   if(x >= r or l >= y)  return ;
  44.   if(x <= l && r <= y){
  45.     lazy[id] = color;
  46.     return ;
  47.   }
  48.   int mid = (l+r)/2;
  49.   shift(id);
  50.   paint(x, y, color, 2 * id, l, mid);
  51.   paint(x, y, color, 2*id+1, mid, r);
  52. }
  53.  
  54. set<int> ans;
  55. void cnt(int id = 1,int l = 0, int r = n){
  56.   if(lazy[id]){
  57.     ans.insert(lazy[id]);
  58.     return ; // there is no need to see the children, because all the interval is from the same color
  59.   }
  60.   if(r == l + 1) return ;
  61.   int mid = (l+r)/2;
  62.   cnt(2 * id, l, mid);
  63.   cnt(2*id+1, mid, r);
  64. }
  65.  
  66. int main() {
  67.   IO_SPEED_UP;
  68.  
  69.   int t; cin >> t;
  70.   while(t--) {
  71.     ans.clear();
  72.     int x; cin >> x;
  73.     set<int> pts;
  74.     vii ranges(x);
  75.     for(int i = 0; i < x; i++) {
  76.       int l, r; cin >> l >> r;
  77.       pts.insert(l);
  78.       pts.insert(r);
  79.       ranges[i] = mp(l, r);
  80.     }
  81.  
  82.     // range compression
  83.     int k = 0;
  84.     map<int, int> m;
  85.     for(auto p: pts) {
  86.       m[p] = k++;
  87.     }
  88.  
  89.     n = k; // setting the total no. of points
  90.     for(int i = 0; i < x; i++) {
  91.       ranges[i].F = m[ranges[i].F];
  92.       ranges[i].S = m[ranges[i].S];
  93.     }
  94.  
  95.     lazy.assign(4 * (k + 1), 0);
  96.  
  97.     for(int i = 0; i < x; i++) {
  98.       paint(ranges[i].F, ranges[i].S + 1, i + 1);
  99.     }
  100.  
  101.     cnt();
  102.     cout << ans.size() << "\n";
  103.   }
  104.   return 0;
  105. }
  106.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin 
1
5
1 4
2 6
8 10
3 4
7 10
stdout 
4
https://ideone.com/10PrW4
SPOJ - POSTERS - LAZY PROPAGATION
language:
C++14 (gcc 8.3)
created:
7 years 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!