oj.uz

Submission #146987

# Submission time Handle Problem Language Result Execution time Memory
146987 2019-08-27T02:31:25 Z dongwon0427 Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 734 ms 142588 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 142588 KB Output is correct
2 Correct 622 ms 142412 KB Output is correct
3 Correct 609 ms 140256 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 7 ms 376 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 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 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 3 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 7 ms 376 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 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 17 ms 3052 KB Output is correct
15 Correct 17 ms 3048 KB Output is correct
16 Correct 17 ms 3048 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 132256 KB Output is correct
2 Correct 579 ms 132328 KB Output is correct
3 Correct 569 ms 132364 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 142588 KB Output is correct
2 Correct 622 ms 142412 KB Output is correct
3 Correct 609 ms 140256 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 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 7 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 17 ms 3052 KB Output is correct
18 Correct 17 ms 3048 KB Output is correct
19 Correct 17 ms 3048 KB Output is correct
20 Correct 583 ms 132256 KB Output is correct
21 Correct 579 ms 132328 KB Output is correct
22 Correct 569 ms 132364 KB Output is correct
23 Correct 734 ms 132288 KB Output is correct
24 Correct 690 ms 134324 KB Output is correct
25 Correct 682 ms 134148 KB Output is correct