Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- int n; // size of heap
- long m[200000]; // heap
- struct gruz{
- int l, t;
- };
- bool operator > (gruz g, gruz f){
- return g.t > f.t;
- }
- bool operator < (gruz g, gruz f){
- return g.t < f.t;
- }
- bool operator <= (gruz g, gruz f){
- return g.t <= f.t;
- }
- bool operator >= (gruz g, gruz f){
- return g.t >= f.t;
- }
- void SiftUp(int i){
- if (i > 1){
- if (m[i] < m[i / 2]) {
- swap(m[i], m[i / 2]);
- SiftUp((i / 2));
- }
- }
- }
- void insert(long a){
- ++n;
- m[n] = a;
- int i = n;
- SiftUp(i);
- }
- void SiftDown(int i){
- if (n >= 2 * i + 1){
- if (m[2 * i] > m[2 * i + 1]){
- if (m[2 * i + 1] < m[i]) {
- swap(m[2 * i + 1], m[i]);
- SiftDown(2 * i + 1);
- }
- }
- else {
- if (m[2 * i] < m[i]) {
- swap(m[2 * i], m[i]);
- SiftDown(2 * i);
- }
- }
- }
- else if (n == 2 * i){
- if (m[2 * i] < m[i]){
- swap(m[2 * i], m[i]);
- SiftDown(2 * i);
- }
- }
- }
- void extract_min(){
- if (n > 0) {
- long min = m[1];
- m[1] = m[n];
- --n;
- if (n > 0) SiftDown(1);
- }
- }
- int main() {
- int N;
- cin >> N;
- gruz g[N];
- int Max = 0;
- for (int i = 0; i < N; ++i){
- cin >> g[i].t >> g[i].l;
- Max = max(Max, g[i].l + g[i].t);
- }
- sort(g, g + N);
- int count = 0;
- int answer = -1;
- for (int i = 0; i <= Max; ++i){
- if (n > 0){
- while (n > 0 && m[1] == i) extract_min();
- }
- while (count < N && g[count].t == i){
- insert(g[count].t + g[count].l);
- count++;
- }
- answer = max(answer, n);
- }
- cout << answer;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement