fork download
copy 
  1. // Warning: very old code.
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. #define VALMAX 100005
  7. using namespace std;
  8.  
  9. struct node {
  10.     int left, right;
  11.     int lazy, maxima;
  12.     node(int _left = 0, int _right = 0, int _lazy = 0, int _maxima = 0) :
  13.       left(_left), right(_right), lazy(_lazy), maxima(_maxima) {}
  14.     inline void make_lazy(int value) {
  15.         maxima += value;
  16.         lazy += value;
  17.     }
  18. } arb[VALMAX * 4];
  19.  
  20. void build(int left, int right, int pos) {
  21.     arb[pos].left = left, arb[pos].right = right;
  22.     arb[pos].lazy = arb[pos].maxima = 0;
  23.     if (left == right)
  24.         return ;
  25.     const int mijl = (left + right) / 2;
  26.     build(left, mijl, 2 * pos);
  27.     build(mijl + 1, right, 2 * pos + 1);
  28. }
  29.  
  30. void update(int left, int right, int value, int pos) {
  31.     if (arb[pos].left == left && arb[pos].right == right) {
  32.         arb[pos].make_lazy(value);
  33.         return ;
  34.     }
  35.     const int mijl = (arb[pos].left + arb[pos].right) / 2;
  36.     if (right <= mijl)
  37.         update(left, right, value, 2 * pos);
  38.     else if (left > mijl)
  39.         update(left, right, value, 2 * pos + 1);
  40.     else {
  41.         update(left, mijl, value, 2 * pos);
  42.         update(mijl + 1, right, value, 2 * pos + 1);
  43.     }
  44.     arb[pos].maxima = max(arb[2 * pos].maxima, arb[2 * pos + 1].maxima) + arb[pos].lazy;
  45. }
  46.  
  47. struct point {
  48.     int x, y;
  49.     point(int _x = 0, int _y = 0): x(_x), y(_y) {}
  50. } points[VALMAX + 5];
  51.  
  52. struct event {
  53.     int type; // 1 = insert, -1 = erase
  54.     int which;
  55.     event(int _type = 0, int _which = 0): type(_type), which(_which) {}
  56. };
  57.  
  58. vector <event> events[VALMAX + 5];
  59.  
  60. int sweep_maxima_OY_asc[VALMAX + 5];
  61. int sweep_maxima_OY_desc[VALMAX + 5];
  62. int sweep_maxima_OX_asc[VALMAX + 5];
  63. int sweep_maxima_OX_desc[VALMAX + 5];
  64.  
  65. int dx, dy, n;
  66. inline void do_sweeping (int *sweep_maxima_OY_asc, int *sweep_maxima_OY_desc) {
  67.     build(0, VALMAX, 1);
  68.  
  69.     for (int i = 1; i <= n; i++) {
  70.         events[points[i].x].push_back(event(1, i));
  71.  
  72.         if (points[i].x + dx <= VALMAX)
  73.             events[points[i].x + dx].push_back(event(-1, i));
  74.     }
  75.  
  76.     vector <event> :: iterator it;
  77.     for (int i = 0; i <= VALMAX; i++) {
  78.         if (i)
  79.             sweep_maxima_OY_asc[i] = sweep_maxima_OY_asc[i - 1];
  80.         for (it = events[i].begin(); it != events[i].end(); it++)
  81.             if (it -> type == 1) {
  82.                 update(points[it -> which].y, min(points[it -> which].y + dy, VALMAX), it -> type, 1);
  83.                 sweep_maxima_OY_asc[i] = max(sweep_maxima_OY_asc[i], arb[1].maxima);
  84.             }
  85.         for (it = events[i].begin(); it != events[i].end(); it++)
  86.             if (it -> type == -1) {
  87.                 update(points[it -> which].y, min(points[it -> which].y + dy, VALMAX), it -> type, 1);
  88.                 sweep_maxima_OY_asc[i] = max(sweep_maxima_OY_asc[i], arb[1].maxima);
  89.             }
  90.         events[i].clear();
  91.     }
  92.  
  93.     //Baleere descendenta
  94.     build(0, VALMAX, 1);
  95.  
  96.     for (int i = 1; i <= n; i++) {
  97.         events[points[i].x].push_back(event(1, i));
  98.         if (points[i].x - dx >= 0)
  99.             events[points[i].x - dx].push_back(event(-1, i));
  100.     }
  101.  
  102.     for (int i = VALMAX; i >= 0; i--) {
  103.         sweep_maxima_OY_desc[i] = sweep_maxima_OY_desc[i + 1];
  104.         for (it = events[i].begin(); it != events[i].end(); it++)
  105.             if (it -> type == 1) {
  106.                 update(points[it -> which].y, min(points[it -> which].y + dy, VALMAX), it -> type, 1);
  107.                 sweep_maxima_OY_desc[i] = max(sweep_maxima_OY_desc[i], arb[1].maxima);
  108.             }
  109.         for (it = events[i].begin(); it != events[i].end(); it++)
  110.             if (it -> type == -1) {
  111.                 update(points[it -> which].y, min(points[it -> which].y + dy, VALMAX), it -> type, 1);
  112.                 sweep_maxima_OY_desc[i] = max(sweep_maxima_OY_desc[i], arb[1].maxima);
  113.             }
  114.         events[i].clear();
  115.     }
  116. }
  117.  
  118. inline void invert () {
  119.     for (int i = 1; i <= n; i++)
  120.         swap(points[i].x, points[i].y);
  121.     swap(dx, dy);
  122. }
  123.  
  124. int main()
  125. {
  126.     ifstream cin("parcele.in");
  127.     ofstream cout("parcele.out");
  128.  
  129.     cin >> dx >> dy >> n;
  130.  
  131.     for (int i = 1; i <= n; i++)
  132.         cin >> points[i].x >> points[i].y;
  133.  
  134.     do_sweeping(sweep_maxima_OY_asc, sweep_maxima_OY_desc);
  135.     invert();
  136.     do_sweeping(sweep_maxima_OX_asc, sweep_maxima_OX_desc);
  137.  
  138.     int maxima = 0;
  139.     for (int i = 0; i < VALMAX; i++) {
  140.         maxima = max(maxima, sweep_maxima_OY_asc[i] + sweep_maxima_OY_desc[i + 1]);
  141.         maxima = max(maxima, sweep_maxima_OX_asc[i] + sweep_maxima_OX_desc[i + 1]);
  142.     }
  143.  
  144.     cout << maxima << '\n';
  145.  
  146.     cin.close();
  147.     cout.close();
  148.     return 0;
  149. }
Success #stdin #stdout 0.01s 14356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MX5s5N
language:
C++14 (gcc 8.3)
created:
6 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!