#include <bits/stdc++.h> using namespace std; #define ll long long int main(){ int n, m, a, b, c, ile; cin >> n >> m; vector <vector <int>> zolty; vector <vector <int>> niebieski; vector <vector <int>> czerwony; vector <vector <int>> nzolty; vector <vector <int>> nniebieski; vector <vector <int>> nczerwony; // vector <int> wyn; ile = 0; for(int i=0; i<=m-1; i++){ cin >> a >> b >> c; if(c == 1){ zolty.push_back({a,b}); }else if(c == 2){ niebieski.push_back({a,b}); }else if(c == 3){ czerwony.push_back({a,b}); } } sort(zolty.begin(), zolty.end()); sort(niebieski.begin(), niebieski.end()); sort(czerwony.begin(), czerwony.end()); if(zolty.size() == 0){ cout << 0; return 0; } int zmin = zolty[0][0]; int zmax = zolty[0][1]; for(int i=0; i<=zolty.size()-1; i++){ // if(zolty[i][0] < zmin){ // continue; // } if(i > 0){ if(zolty[i][0]<=zmax){ if(zolty[i][1] < zmax+1){ continue; }else{ zmin = zmax+1; zmax = zolty[i][1]; } }else{ zmin = zolty[i][0]; zmax = zolty[i][1]; } } nzolty.push_back({zmin,zmax}); // cout << zmin << " " << zmax << endl; } if(niebieski.size() == 0){ cout << 0; return 0; } int nmin = niebieski[0][0]; int nmax = niebieski[0][1]; for(int i=0; i<=niebieski.size()-1; i++){ // if(zolty[i][0] < zmin){ // continue; // } if(i > 0){ if(niebieski[i][0]<=nmax){ if(niebieski[i][1] < nmax+1){ continue; }else{ nmin = nmax+1; nmax = niebieski[i][1]; } }else{ nmin = niebieski[i][0]; nmax = niebieski[i][1]; } } nniebieski.push_back({nmin,nmax}); // cout << nmin << " " << nmax << endl; } int cmin = czerwony[0][0]; int cmax = czerwony[0][1]; for(int i=0; i<=czerwony.size()-1; i++){ // if(zolty[i][0] < zmin){ // continue; // } if(i > 0){ if(czerwony[i][0]<=cmax){ if(czerwony[i][1] < cmax+1){ continue; }else{ cmin = cmax+1; cmax = czerwony[i][1]; } }else{ cmin = czerwony[i][0]; cmax = czerwony[i][1]; } } nczerwony.push_back({cmin,cmax}); // cout << cmin << " " << cmax << endl; } int minim, maxim, mi, ma; for(int i=0; i<=nzolty.size()-1; i++){ for(int j=0; j<=nniebieski.size()-1; j++){ if(nzolty[i][0] <= nniebieski[j][1] && nzolty[i][1] >= nniebieski[j][0]){ mi = max(nzolty[i][0], nniebieski[j][0]); ma = min(nzolty[i][1], nniebieski[j][1]); ile+=(ma-mi +1); for(int k=0; k<=nczerwony.size()-1; k++){ if(mi <= nczerwony[k][1] && ma >= nczerwony[k][0]){ minim = max(mi, nczerwony[k][0]); maxim = min(ma, nczerwony[k][1]); ile-= (maxim-minim + 1); } } } } } cout << ile; 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 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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | #include <bits/stdc++.h> using namespace std; #define ll long long int main(){ int n, m, a, b, c, ile; cin >> n >> m; vector <vector <int>> zolty; vector <vector <int>> niebieski; vector <vector <int>> czerwony; vector <vector <int>> nzolty; vector <vector <int>> nniebieski; vector <vector <int>> nczerwony; // vector <int> wyn; ile = 0; for(int i=0; i<=m-1; i++){ cin >> a >> b >> c; if(c == 1){ zolty.push_back({a,b}); }else if(c == 2){ niebieski.push_back({a,b}); }else if(c == 3){ czerwony.push_back({a,b}); } } sort(zolty.begin(), zolty.end()); sort(niebieski.begin(), niebieski.end()); sort(czerwony.begin(), czerwony.end()); if(zolty.size() == 0){ cout << 0; return 0; } int zmin = zolty[0][0]; int zmax = zolty[0][1]; for(int i=0; i<=zolty.size()-1; i++){ // if(zolty[i][0] < zmin){ // continue; // } if(i > 0){ if(zolty[i][0]<=zmax){ if(zolty[i][1] < zmax+1){ continue; }else{ zmin = zmax+1; zmax = zolty[i][1]; } }else{ zmin = zolty[i][0]; zmax = zolty[i][1]; } } nzolty.push_back({zmin,zmax}); // cout << zmin << " " << zmax << endl; } if(niebieski.size() == 0){ cout << 0; return 0; } int nmin = niebieski[0][0]; int nmax = niebieski[0][1]; for(int i=0; i<=niebieski.size()-1; i++){ // if(zolty[i][0] < zmin){ // continue; // } if(i > 0){ if(niebieski[i][0]<=nmax){ if(niebieski[i][1] < nmax+1){ continue; }else{ nmin = nmax+1; nmax = niebieski[i][1]; } }else{ nmin = niebieski[i][0]; nmax = niebieski[i][1]; } } nniebieski.push_back({nmin,nmax}); // cout << nmin << " " << nmax << endl; } int cmin = czerwony[0][0]; int cmax = czerwony[0][1]; for(int i=0; i<=czerwony.size()-1; i++){ // if(zolty[i][0] < zmin){ // continue; // } if(i > 0){ if(czerwony[i][0]<=cmax){ if(czerwony[i][1] < cmax+1){ continue; }else{ cmin = cmax+1; cmax = czerwony[i][1]; } }else{ cmin = czerwony[i][0]; cmax = czerwony[i][1]; } } nczerwony.push_back({cmin,cmax}); // cout << cmin << " " << cmax << endl; } int minim, maxim, mi, ma; for(int i=0; i<=nzolty.size()-1; i++){ for(int j=0; j<=nniebieski.size()-1; j++){ if(nzolty[i][0] <= nniebieski[j][1] && nzolty[i][1] >= nniebieski[j][0]){ mi = max(nzolty[i][0], nniebieski[j][0]); ma = min(nzolty[i][1], nniebieski[j][1]); ile+=(ma-mi +1); for(int k=0; k<=nczerwony.size()-1; k++){ if(mi <= nczerwony[k][1] && ma >= nczerwony[k][0]){ minim = max(mi, nczerwony[k][0]); maxim = min(ma, nczerwony[k][1]); ile-= (maxim-minim + 1); } } } } } cout << ile; return 0; } |