oj.uz

Submission #146983

# Submission time Handle Problem Language Result Execution time Memory
146983 2019-08-27T02:26:52 Z dongwon0427 Lightning Rod (NOI18_lightningrod) C++14
80 / 100
 2000 ms 143252 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;


int n;

//https://www.geeksforgeeks.org/fast-io-for-competitive-programming/
void fastscan(int &number)
{
    //variable to indicate sign of input number
    bool negative = false;
    register int c;

    number = 0;

    // extract current character from buffer
    c = getchar();
    if (c=='-')
    {
        // number is negative
        negative = true;

        // extract the next character from the buffer
        c = getchar();
    }

    // Keep on extracting characters if they are integers
    // i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;

    // if scanned input has a negative sign, negate the
    // value of the input number
    if (negative)
        number *= -1;
}
vector<pii> v;
int main() {
    fastscan(n);
    pii prv = pii(-1,0);
    for(int i=0;i<n;i++) {
        int t1,t2;
        fastscan(t1); fastscan(t2);
        if(t1 != prv.first) {
            prv = pii(t1,t2);
            v.push_back(prv);
        }  else if(prv.second < t2) {
            prv.second = t2;
            v.back().second = t2;
        }
    }

    vector<int> s;
    s.push_back(0);
    int mx = v[0].first + v[0].second;
    for(int i=1;i<v.size();i++) {
        pii p = v[i];
        if(mx >= p.first + p.second) continue;
        mx = p.first + p.second;
        while(!s.empty()) {
            pii t = v[s.back()];
            if(t.second - t.first <= p.second - p.first) s.pop_back();
            else break;
        }
        s.push_back(i);
        //for(int x : s) cout<<x<<' ';
        //cout<<'\n';
    }
    cout<<s.size();
    return 0;
}

Compilation message

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<v.size();i++) {
                 ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1921 ms 142152 KB Output is correct
2 Correct 1901 ms 143252 KB Output is correct
3 Correct 1862 ms 141476 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 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 256 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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 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 256 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 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 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 256 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 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 57 ms 4176 KB Output is correct
15 Correct 55 ms 4228 KB Output is correct
16 Correct 48 ms 4200 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1697 ms 131852 KB Output is correct
2 Correct 1705 ms 133244 KB Output is correct
3 Correct 1667 ms 132956 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1921 ms 142152 KB Output is correct
2 Correct 1901 ms 143252 KB Output is correct
3 Correct 1862 ms 141476 KB Output is correct
4 Correct 2 ms 256 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 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 57 ms 4176 KB Output is correct
18 Correct 55 ms 4228 KB Output is correct
19 Correct 48 ms 4200 KB Output is correct
20 Correct 1697 ms 131852 KB Output is correct
21 Correct 1705 ms 133244 KB Output is correct
22 Correct 1667 ms 132956 KB Output is correct
23 Execution timed out 2044 ms 68500 KB Time limit exceeded
24 Halted 0 ms 0 KB -