Submission #245924

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
245924	2020-07-07T19:46:49 Z	zecookiez	Lightning Rod (NOI18_lightningrod)	C++14	76 / 100	2000 ms	198072 KB

lightningrod

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<pair<int, int>> st;
    for(int x, y, i = 0; i < n; ++i){
        cin >> x >> y;
        bool add = true;
        while(!st.empty()){
            // current building bad
            if(x + y <= st.back().second + st.back().first){ add = false; break; }
            // previous building bad
            if(x - y <= st.back().first - st.back().second){ st.pop_back();}
            else break;
        }
        if(add) st.emplace_back(x, y);
    }
    cout << st.size() << "\n";
    return 0;
}

Subtask #1

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2068 ms	198072 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

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	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 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	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 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	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 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	384 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	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 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	384 KB	Output is correct
14	Correct	58 ms	3960 KB	Output is correct
15	Correct	56 ms	3704 KB	Output is correct
16	Correct	51 ms	3956 KB	Output is correct

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1935 ms	120612 KB	Output is correct
2	Correct	1943 ms	116216 KB	Output is correct
3	Correct	1888 ms	114548 KB	Output is correct

Subtask #7

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2068 ms	198072 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-