Submission #146983

#	Time	Username	Problem	Language	Result	Execution time	Memory
146983		dongwon0427	Lightning Rod (NOI18_lightningrod)	C++14	80 / 100	2044 ms	143252 KiB

Main

#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 (stderr)

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 / 4
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 26 / 26
• Subtask 6: 10 / 10
• Subtask 7: 0 / 20