oj.uz

Submission #95192

# Submission time Handle Problem Language Result Execution time Memory
95192 2019-01-28T12:58:07 Z win11905 Lightning Rod (NOI18_lightningrod) C++14
66 / 100
 2000 ms 132040 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define iii tuple<int, int, int>
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};


class lightningrod {
private:
    int n;
    stack<pii> stk;
    bool check_cover(pii a, pii b) {
        return abs(a.x - b.x) <= a.y - b.y;
    }
public:
    void solve(istream& cin, ostream& cout) {
        cin >> n;
        vector<pii> vec;
        for(int i = 0, a, b; i < n; ++i) {
            cin >> a >> b;
            vec.emplace_back(a, b);
        }
        sort(vec.begin(), vec.end(), [&](const pii &a, const pii &b) {
            if(a.x == b.x) return a.y > b.y;
            return a.x < b.x;
        });
        for(auto v : vec) {
            if(stk.empty()) {
                stk.emplace(v);
                continue;
            }
            if(check_cover(stk.top(), v)) continue;
            while(!stk.empty() && check_cover(v, stk.top())) stk.pop();
            stk.emplace(v);
        }
        cout << stk.size() << endl;
    }
};

class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        lightningrod *obj = new lightningrod();
        obj->solve(in, out);
    }
};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 292 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 50 ms 3044 KB Output is correct
15 Correct 49 ms 3076 KB Output is correct
16 Correct 46 ms 3056 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 20.0

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