#include <bits/stdc++.h> using namespace std; typedef set<unsigned long long>::iterator iy; int a,raz[300001],pol[300001],odp,pomox; vector<int>minen[3000]; set<unsigned long long>odpowiedzi; unsigned long long akto,dosp; int mamy[3001]; unsigned long long dwa[3001]; bool juzdodalem[100][100]; void dynamik(int ter) { iy it=odpowiedzi.lower_bound(akto); if(it==odpowiedzi.end()) { ++odp; odpowiedzi.insert(akto); } else { dosp=*it; if(akto!=dosp) { ++odp; odpowiedzi.insert(akto); } } if(ter!=a-1) dynamik(ter+1); for(int i=0;i<minen[ter].size();++i) { if(mamy[minen[ter][i]]==0) { akto+=dwa[minen[ter][i]]; } mamy[minen[ter][i]]++; } it=odpowiedzi.lower_bound(akto); if(it==odpowiedzi.end()) { ++odp; odpowiedzi.insert(akto); } else { dosp=*it; if(akto!=dosp) { ++odp; odpowiedzi.insert(akto); } } if(ter!=a-1) dynamik(ter+1); for(int i=0;i<minen[ter].size();++i) { mamy[minen[ter][i]]--; if(mamy[minen[ter][i]]==0) { akto-=dwa[minen[ter][i]]; } } } void dfs(int ter,int dotego) { for(int i=0;i<minen[ter].size();++i) { if(juzdodalem[dotego][minen[ter][i]]==0) { juzdodalem[dotego][minen[ter][i]]=1; minen[dotego].push_back(minen[ter][i]); dfs(minen[ter][i],dotego); } } } int main() { scanf("%d",&a); if(a>35) { printf("%d",1); return 0; } dwa[0]=1; for(int i=1;i<64;++i) dwa[i]=dwa[i-1]*2; for(int i=0;i<a;++i) { minen[i].push_back(i); scanf("%d%d",&pol[i],&raz[i]); for(int j=i-1;j>=0;--j) { if(pol[i]-raz[i]<=pol[j]) { minen[i].push_back(j); juzdodalem[i][j]=1; } if(pol[j]+raz[j]>=pol[i]) { minen[j].push_back(i); juzdodalem[j][i]=1; } } } for(int i=0;i<a;++i) { pomox=minen[i].size(); for(int j=0;j<pomox;++j) { dfs(minen[i][j],i); } } dynamik(0); printf("%d",odp); 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 | #include <bits/stdc++.h> using namespace std; typedef set<unsigned long long>::iterator iy; int a,raz[300001],pol[300001],odp,pomox; vector<int>minen[3000]; set<unsigned long long>odpowiedzi; unsigned long long akto,dosp; int mamy[3001]; unsigned long long dwa[3001]; bool juzdodalem[100][100]; void dynamik(int ter) { iy it=odpowiedzi.lower_bound(akto); if(it==odpowiedzi.end()) { ++odp; odpowiedzi.insert(akto); } else { dosp=*it; if(akto!=dosp) { ++odp; odpowiedzi.insert(akto); } } if(ter!=a-1) dynamik(ter+1); for(int i=0;i<minen[ter].size();++i) { if(mamy[minen[ter][i]]==0) { akto+=dwa[minen[ter][i]]; } mamy[minen[ter][i]]++; } it=odpowiedzi.lower_bound(akto); if(it==odpowiedzi.end()) { ++odp; odpowiedzi.insert(akto); } else { dosp=*it; if(akto!=dosp) { ++odp; odpowiedzi.insert(akto); } } if(ter!=a-1) dynamik(ter+1); for(int i=0;i<minen[ter].size();++i) { mamy[minen[ter][i]]--; if(mamy[minen[ter][i]]==0) { akto-=dwa[minen[ter][i]]; } } } void dfs(int ter,int dotego) { for(int i=0;i<minen[ter].size();++i) { if(juzdodalem[dotego][minen[ter][i]]==0) { juzdodalem[dotego][minen[ter][i]]=1; minen[dotego].push_back(minen[ter][i]); dfs(minen[ter][i],dotego); } } } int main() { scanf("%d",&a); if(a>35) { printf("%d",1); return 0; } dwa[0]=1; for(int i=1;i<64;++i) dwa[i]=dwa[i-1]*2; for(int i=0;i<a;++i) { minen[i].push_back(i); scanf("%d%d",&pol[i],&raz[i]); for(int j=i-1;j>=0;--j) { if(pol[i]-raz[i]<=pol[j]) { minen[i].push_back(j); juzdodalem[i][j]=1; } if(pol[j]+raz[j]>=pol[i]) { minen[j].push_back(i); juzdodalem[j][i]=1; } } } for(int i=0;i<a;++i) { pomox=minen[i].size(); for(int j=0;j<pomox;++j) { dfs(minen[i][j],i); } } dynamik(0); printf("%d",odp); return 0; } |