Submission #146987

#	Time	Username	Problem	Language	Result	Execution time	Memory
146987		dongwon0427	Lightning Rod (NOI18_lightningrod)	C++14	100 / 100	734 ms	142588 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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


int n;
static char buf[1 << 19]; // size : any number geq than 1024
static int idx = 0;
static int bytes = 0;
static inline int _read() {
	if (!bytes || idx == bytes) {
		bytes = (int)fread(buf, sizeof(buf[0]), sizeof(buf), stdin);
		idx = 0;
	}
	return buf[idx++];
}
static inline int fastscan() {
	int x = 0, s = 1;
	int c = _read();
	while (c <= 32) c = _read();
	if (c == '-') s = -1, c = _read();
	while (c > 32) x = 10 * x + (c - '0'), c = _read();
	if (s < 0) x = -x;
	return x;
}

vector<pii> v;
int main() {
    n=fastscan();
    pii prv = pii(-1,0);
    for(int i=0;i<n;i++) {
        int t1,t2;
        t1=fastscan(); t2=fastscan();
        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:49: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: 20 / 20