Submission #654974

#	Time	Username	Problem	Language	Result	Execution time	Memory
654974		valerikk	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	475 ms	246188 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#include <cstdio>

/** Interface */

inline int readChar();
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);

/** Read */

static const int buf_size = 4096;

inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
    if (pos == len) return -1;
    return buf[pos++];
}

inline int readChar() {
    int c = getChar();
    while (c <= 32) c = getChar();
    return c;
}

template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-') s = -1, c = getChar();
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}

/** Write */

static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar(int x) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}

template <class T>
inline void writeInt(T x, char end) {
    if (x < 0) writeChar('-'), x = -x;

    char s[24];
    int n = 0;
    while (x || !n) s[n++] = '0' + x % 10, x /= 10;
    while (n--) writeChar(s[n]);
    if (end) writeChar(end);
}

inline void writeWord(const char *s) {
    while (*s) writeChar(*s++);
}

struct Flusher {
    ~Flusher() {
        if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;

void flush() {
    if (write_pos) {
        fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
}

const int N = 1e7 + 7;

int n;
int x[N], y[N];
int st[N], top = 0;

bool protect(int i, int j) {
	return abs(x[i] - x[j]) <= y[i] - y[j];
}

int main() {
	n = readInt();
	for (int i = 0; i < n; ++i) {
		x[i] = readInt();
		y[i] = readInt();
	}
	for (int i = 0; i < n; ++i) {
		while (top > 0 && protect(i, st[top - 1])) {
			--top;
		}
		if (top == 0 || !protect(st[top - 1], i)) {
			st[top++] = i;
		}
	}
	writeInt(top, '\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