Submission #246304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
246304	2020-07-08T15:32:40 Z	SamAnd	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	417 ms	86392 KB

lightningrod

#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;

inline int ka()
{
    int x = 0;
    while (1)
    {
        char y = getchar_unlocked();
        if ('0' <= y && y <= '9')
            x = (x * 10) + (y - '0');
        else
            return x;
    }
}

int m;
int xx[N], yy[N];

void solv()
{
    int nn = ka();
    int x, y;
    while (nn--)
    {
        x = ka();
        y = ka();
        while (m && x - xx[m - 1] <= y - yy[m - 1])
            m--;
        if (!m || !(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){}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	221 ms	77560 KB	Output is correct
2	Correct	223 ms	76972 KB	Output is correct
3	Correct	233 ms	74744 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct

Subtask #4

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	640 KB	Output is correct

Subtask #5

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	640 KB	Output is correct
14	Correct	13 ms	1152 KB	Output is correct
15	Correct	13 ms	1152 KB	Output is correct
16	Correct	12 ms	1792 KB	Output is correct

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	241 ms	50392 KB	Output is correct
2	Correct	234 ms	50560 KB	Output is correct
3	Correct	227 ms	49272 KB	Output is correct

Subtask #7

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	221 ms	77560 KB	Output is correct
2	Correct	223 ms	76972 KB	Output is correct
3	Correct	233 ms	74744 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	5 ms	640 KB	Output is correct
17	Correct	13 ms	1152 KB	Output is correct
18	Correct	13 ms	1152 KB	Output is correct
19	Correct	12 ms	1792 KB	Output is correct
20	Correct	241 ms	50392 KB	Output is correct
21	Correct	234 ms	50560 KB	Output is correct
22	Correct	227 ms	49272 KB	Output is correct
23	Correct	417 ms	1472 KB	Output is correct
24	Correct	391 ms	77648 KB	Output is correct
25	Correct	361 ms	86392 KB	Output is correct