usaco/milk2.cpp at master · wdskuki/usaco · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*
ID: dswei191
LANG: C++
TASK: milk2
*/

#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

int n;
class Duration{
public:
    int st,et;
    Duration(int st, int et){
        this->st = st;
        this->et = et;
    }

};
list<Duration> ldut;
vector<Duration> vdut;
int ret1 = 0;
int ret2 = 0;
bool compare(Duration a, Duration b){
    return a.st < b.st;
}
int main(){
    ofstream fout("milk2.out");
    ifstream fin("milk2.in");

    fin >> n;
    int st, et;

    for(int i = 0; i < n; i++){
        fin >> st >> et;
        Duration d(st, et);
        vdut.push_back(d);
    }

    sort(vdut.begin(), vdut.end(), compare);

//    for(int i = 0; i < n; i++){
//        cout << vdut[i].st << ' ' << vdut[i].et <<endl;
//    }

    for(int i = 0; i < n; i++){
        ldut.push_back(vdut[i]);
    }
//
//    list<Duration>::iterator itStart;
    list<Duration>::iterator itStart = ldut.begin();
    list<Duration>::iterator it;
//    itStart = ldut.begin();
    for(it = ldut.begin(); it != ldut.end();){
        if(it == itStart){
            it++;
            continue;
        }
        if(it->st > itStart->et){
            itStart = it;
            it++;
        }else{
            itStart->et = max(itStart->et, it->et);
            it = ldut.erase(it);
        }
    }

//    for(it = ldut.begin(); it != ldut.end(); it++){
//        cout << it->st << ' ' << it->et <<endl;
//    }
    list<Duration>::iterator itNext;
    for(it = ldut.begin(); it != ldut.end(); it++){
        ret1 = max(ret1, it->et - it->st);
        itNext = it;
        itNext++;
        if(itNext != ldut.end()){
            ret2 = max(ret2, itNext->st - it->et);
        }
    }

    fout<< ret1 << ' ' << ret2 <<endl;
    return 0;
}