oj.uz

Submission #538931

# Submission time Handle Problem Language Result Execution time Memory
538931 2022-03-18T04:42:38 Z ac2hu Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 383 ms 207632 KB 
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
inline int readChar();
template <class T = long long> 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;
signed main() {
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int n = readInt();
	vector<pair<int,int>> a(n);
	for(auto &e : a){
		e.first = readInt();
		e.second = readInt();
	}
	auto fit = [&](pair<int,int> a,pair<int,int> b) -> bool{
		// if b can't fit a 
		return (abs(b.first  - a.first) <= abs(b.second - a.second));
	};
	auto better = [&](pair<int,int> a, pair<int,int> b) -> bool{
		if(a.first + a.second > b.first + b.second)
			return true;
		return false;
	};
	vector<pair<int,int>> st;
	st.push_back(a[0]);
	for(int i = 1;i<n;i++){
		while(st.size() > 0 && fit(a[i], st.back()) && better(a[i], st.back()))
			st.pop_back();
		if(st.size() == 0 || (!fit(a[i], st.back()) && !better(st.back(), a[i]))){
			st.push_back(a[i]);
		}
		// if(st.size() > 0 && fit(a[i], st.top()) && ){
		// }
		// else{
			// while(st.size() > 0 && fit(a[]))
		// }
		deb(st);
	}
	cout << st.size() << "\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 207632 KB Output is correct
2 Correct 327 ms 207396 KB Output is correct
3 Correct 354 ms 205504 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 10 ms 4180 KB Output is correct
15 Correct 10 ms 4292 KB Output is correct
16 Correct 10 ms 5328 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 144044 KB Output is correct
2 Correct 349 ms 144324 KB Output is correct
3 Correct 338 ms 142448 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 207632 KB Output is correct
2 Correct 327 ms 207396 KB Output is correct
3 Correct 354 ms 205504 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 10 ms 4180 KB Output is correct
18 Correct 10 ms 4292 KB Output is correct
19 Correct 10 ms 5328 KB Output is correct
20 Correct 362 ms 144044 KB Output is correct
21 Correct 349 ms 144324 KB Output is correct
22 Correct 338 ms 142448 KB Output is correct
23 Correct 383 ms 72132 KB Output is correct
24 Correct 361 ms 71928 KB Output is correct
25 Correct 369 ms 76824 KB Output is correct