# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
246215 | SamAnd | Lightning Rod (NOI18_lightningrod) | C++17 | 2091 ms | 76244 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 10000007;
int ka()
{
int x = 0;
while (1)
{
char y = getchar();
if ('0' <= y && y <= '9')
x = (x * 10) + (y - '0');
else
return x;
}
}
int m;
int xx[N], yy[N];
void solv()
{
int nn;
//nn = ka();
scanf("%d", &nn);
while (nn--)
{
int x, y;
//x = ka();
//y = ka();
scanf("%d%d", &x, &y);
if (m == 0)
{
xx[m] = x;
yy[m] = y;
m++;
continue;
}
if (x - xx[m - 1] <= y - yy[m - 1])
{
while (m && x - xx[m - 1] <= y - yy[m - 1])
m--;
xx[m] = x;
yy[m] = y;
m++;
}
else
{
if (!(x - xx[m - 1] <= yy[m - 1] - y))
{
xx[m] = x;
yy[m] = y;
m++;
}
}
}
printf("%d\n", m);
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
//ios_base::sync_with_stdio(false), cin.tie(0);
solv();
return 0;
}
//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |