#include <bits/stdc++.h> using namespace std; constexpr int MAX=5e5+2; pair<int,int>pol_czas_y[MAX]; pair<int,int>pol_czas_x[MAX]; vector<bool>kolizja_y[MAX]; vector<bool>kolizja_x[MAX]; int ilosc_zderzen[MAX]; int prefix_zderzen[MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int liczba_dostaw,i,ile_z_x{0},ile_z_y{0},j,polozenie,czas; int ile_kolizji_na_ulicy,ile_kolizji{0},index_kolizji{0}; long long ile_usuniec{0},min_usuniec{500000}; char rodzaj_dostawy; cin>>liczba_dostaw; for(i=1; i<=liczba_dostaw; ++i) { cin>>rodzaj_dostawy>>polozenie>>czas; if(rodzaj_dostawy=='1') pol_czas_x[++ile_z_x]=make_pair(polozenie,czas); else pol_czas_y[++ile_z_y]=make_pair(polozenie,czas); } for(i=1; i<=ile_z_y; ++i) { for(j=1; j<=ile_z_x; ++j) { if((pol_czas_y[i].second+pol_czas_x[j].first) == (pol_czas_y[i].first+pol_czas_x[j].second)) { kolizja_y[i].push_back(true); kolizja_x[j].push_back(true); } } } for(i=1; i<=ile_z_y; ++i) { ile_kolizji_na_ulicy=kolizja_y[i].size(); ile_kolizji+=ile_kolizji_na_ulicy; if(ile_kolizji_na_ulicy==0) continue; ilosc_zderzen[index_kolizji++]=ile_kolizji_na_ulicy; } for(i=1; i<=ile_z_x; ++i) { ile_kolizji_na_ulicy=kolizja_x[i].size(); if(ile_kolizji_na_ulicy==0) continue; ilosc_zderzen[index_kolizji++]=ile_kolizji_na_ulicy; } sort(ilosc_zderzen,ilosc_zderzen+index_kolizji); for(i=0; i<index_kolizji; ++i) { prefix_zderzen[i]=prefix_zderzen[i-1]+ilosc_zderzen[i]; ++ile_usuniec; if(prefix_zderzen[i]==ile_kolizji) { if((ile_usuniec < min_usuniec)) min_usuniec=ile_usuniec; prefix_zderzen[i]=0; ile_usuniec=0; } } if(min_usuniec==500000) min_usuniec=0; cout<<min_usuniec<<endl; return 0; }
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 | #include <bits/stdc++.h> using namespace std; constexpr int MAX=5e5+2; pair<int,int>pol_czas_y[MAX]; pair<int,int>pol_czas_x[MAX]; vector<bool>kolizja_y[MAX]; vector<bool>kolizja_x[MAX]; int ilosc_zderzen[MAX]; int prefix_zderzen[MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int liczba_dostaw,i,ile_z_x{0},ile_z_y{0},j,polozenie,czas; int ile_kolizji_na_ulicy,ile_kolizji{0},index_kolizji{0}; long long ile_usuniec{0},min_usuniec{500000}; char rodzaj_dostawy; cin>>liczba_dostaw; for(i=1; i<=liczba_dostaw; ++i) { cin>>rodzaj_dostawy>>polozenie>>czas; if(rodzaj_dostawy=='1') pol_czas_x[++ile_z_x]=make_pair(polozenie,czas); else pol_czas_y[++ile_z_y]=make_pair(polozenie,czas); } for(i=1; i<=ile_z_y; ++i) { for(j=1; j<=ile_z_x; ++j) { if((pol_czas_y[i].second+pol_czas_x[j].first) == (pol_czas_y[i].first+pol_czas_x[j].second)) { kolizja_y[i].push_back(true); kolizja_x[j].push_back(true); } } } for(i=1; i<=ile_z_y; ++i) { ile_kolizji_na_ulicy=kolizja_y[i].size(); ile_kolizji+=ile_kolizji_na_ulicy; if(ile_kolizji_na_ulicy==0) continue; ilosc_zderzen[index_kolizji++]=ile_kolizji_na_ulicy; } for(i=1; i<=ile_z_x; ++i) { ile_kolizji_na_ulicy=kolizja_x[i].size(); if(ile_kolizji_na_ulicy==0) continue; ilosc_zderzen[index_kolizji++]=ile_kolizji_na_ulicy; } sort(ilosc_zderzen,ilosc_zderzen+index_kolizji); for(i=0; i<index_kolizji; ++i) { prefix_zderzen[i]=prefix_zderzen[i-1]+ilosc_zderzen[i]; ++ile_usuniec; if(prefix_zderzen[i]==ile_kolizji) { if((ile_usuniec < min_usuniec)) min_usuniec=ile_usuniec; prefix_zderzen[i]=0; ile_usuniec=0; } } if(min_usuniec==500000) min_usuniec=0; cout<<min_usuniec<<endl; return 0; } |