Submission #668633

#	Time	Username	Problem	Language	Result	Execution time	Memory
668633		600Mihnea	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	583 ms	76056 KiB

Main

#include <bits/stdc++.h>


using namespace std;

inline void read(int& x) {
    x = 0;
    char ch = getchar();
    while (ch&16){
		x = (x << 3) + (x << 1) + (ch&15);
		ch = getchar();
	}
}


struct T
{
  int x;
  int y;
};

bool eat(T a, T b)
{
  return a.x <= b.x && a.y <= b.y;
}

signed main()
{
  int n;
  read(n);
  vector<T> stk;
  stk.reserve(n);
  for (int i = 1; i <= n; i++)
  {
    int x, y;
    read(x);
    read(y);
    T cur = {-x - y, x - y};
    if (stk.empty())
    {
      stk.push_back(cur);
    }
    else
    {
      if (eat(stk.back(), cur))
      {
        continue;
      }
      while (!stk.empty() && eat(cur, stk.back()))
      {
        stk.pop_back();
      }
      stk.push_back(cur);
    }
  }
  cout << (int) stk.size() << "\n";
  return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 26 / 26
• Subtask 6: 10 / 10
• Subtask 7: 20 / 20