#include <iostream> using namespace std; long long mi[1000000]; long long mx[1000000]; long long n,najw=-1; long long licz=0; void szukaj (long long lewy,long long prawy,long long ile,long long b,long long nast) { for (long long k=nast;k<=n-1;k++) { if(mi[k]>lewy) { lewy=mi[k]; } if (mx[k]<prawy) { prawy=mx[k]; } if (lewy>prawy) { break; } if ((k-b+1>=lewy)&&(k-b+1<=prawy)) { if (k==n-1) { if (ile+1>=najw) { if (ile+1==najw) { licz++; licz=licz%1000000007; } else { najw=ile+1; licz=1; } } break; } szukaj(0,1000001,ile+1,k+1,k+1); } else { if(prawy+b-1<k) { break; } } if (n-1-(k)<najw-ile) { break; } } } int main() { ios_base::sync_with_stdio(0); cin>>n; for (int k=0;k<n;k++) { cin>>mi[k]>>mx[k]; } szukaj(0,1000001,0,0,0); if (najw==-1) { cout<<"NIE"<<"\n"; } else { cout<<najw<<" "<<licz<<"\n"; } }
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include <iostream> using namespace std; long long mi[1000000]; long long mx[1000000]; long long n,najw=-1; long long licz=0; void szukaj (long long lewy,long long prawy,long long ile,long long b,long long nast) { for (long long k=nast;k<=n-1;k++) { if(mi[k]>lewy) { lewy=mi[k]; } if (mx[k]<prawy) { prawy=mx[k]; } if (lewy>prawy) { break; } if ((k-b+1>=lewy)&&(k-b+1<=prawy)) { if (k==n-1) { if (ile+1>=najw) { if (ile+1==najw) { licz++; licz=licz%1000000007; } else { najw=ile+1; licz=1; } } break; } szukaj(0,1000001,ile+1,k+1,k+1); } else { if(prawy+b-1<k) { break; } } if (n-1-(k)<najw-ile) { break; } } } int main() { ios_base::sync_with_stdio(0); cin>>n; for (int k=0;k<n;k++) { cin>>mi[k]>>mx[k]; } szukaj(0,1000001,0,0,0); if (najw==-1) { cout<<"NIE"<<"\n"; } else { cout<<najw<<" "<<licz<<"\n"; } } |