USACO-Solutions/crossings.cpp at master · Akshaj1234512/USACO-Solutions · 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
#include <iostream>
#include <algorithm>
using namespace std;

struct cows{

    int start;
    int end;

};

bool cowscomp(cows a, cows b){

    return a.start<b.start;

}

int main(){

    int n;

    cin >> n;

    cows crossings[n];

    int maxxpos[n], minnpos[n];

    for(int i=0; i<n; i++){
        cin >> crossings[i].start >> crossings[i].end;
    }

    sort(crossings, crossings+n, cowscomp);

//    for(int i=0; i<n; i++){
//
//        cout << crossings[i].start << " " << crossings[i].end << endl;
//
//    }

    int cowcounter=0, minn=1000000, maxx=-1000000;

    for(int i=n-1; i>=0; i--){

        if(crossings[i].end<minn) minn=crossings[i].end;

        maxxpos[i]=minn;

    }

    for(int i=0; i<n; i++){

        if(crossings[i].end>maxx) maxx=crossings[i].end;

        minnpos[i]=maxx;

    }

    for(int i=0; i<n; i++){

//        cout << maxxpos[i] << " " << minnpos[i] << endl;

        if(maxxpos[i]>=crossings[i].end and crossings[i].end>=minnpos[i]) cowcounter++;
//            cout << i << endl;

    }

    cout << cowcounter << endl;

    return 0;
}