oj.uz

Submission #379921

# Submission time Handle Problem Language Result Execution time Memory
379921 2021-03-19T17:19:14 Z rocks03 Lightning Rod (NOI18_lightningrod) C++14
80 / 100
 2000 ms 243820 KB 
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve(){
    int N; cin >> N;
    vector<int> x(N), y(N);
    rep(i, 0, N) cin >> x[i] >> y[i];
    deque<int> q;
    q.push_back(0);
    rep(i, 1, N){
        while(SZ(q) && x[i] - y[i] <= x[q.back()] - y[q.back()])
            q.pop_back();
        q.push_back(i);
    }
    int ans = 0;
    while(SZ(q)){
        int v = q[0];
        q.front();
        ans++;
        while(SZ(q) && x[v] + y[v] >= x[q[0]] + y[q[0]]){
            q.pop_front();
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1965 ms 228752 KB Output is correct
2 Correct 1863 ms 228388 KB Output is correct
3 Correct 1846 ms 221928 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 59 ms 5356 KB Output is correct
15 Correct 61 ms 5228 KB Output is correct
16 Correct 47 ms 4972 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1933 ms 205352 KB Output is correct
2 Correct 1876 ms 205192 KB Output is correct
3 Correct 1838 ms 200704 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1965 ms 228752 KB Output is correct
2 Correct 1863 ms 228388 KB Output is correct
3 Correct 1846 ms 221928 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 59 ms 5356 KB Output is correct
18 Correct 61 ms 5228 KB Output is correct
19 Correct 47 ms 4972 KB Output is correct
20 Correct 1933 ms 205352 KB Output is correct
21 Correct 1876 ms 205192 KB Output is correct
22 Correct 1838 ms 200704 KB Output is correct
23 Execution timed out 2078 ms 243820 KB Time limit exceeded
24 Halted 0 ms 0 KB -