Submission #668631

#	Time	Username	Problem	Language	Result	Execution time	Memory
668631		600Mihnea	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1585 ms	76896 KiB

Main

#include <bits/stdc++.h>


using namespace std;

struct T
{
  int x;
  int y;
};

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

signed main()
{
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#endif // ONPC

#ifndef ONPC
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  int n;

  cin >> n;
  vector<T> stk;
  stk.reserve(n);
  for (int i = 1; i <= n; i++)
  {
    int x, y;
    cin >> x >> 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