Unfortunately we were unable to fully decode your file, as it is not encoded in UTF-8.
You can try to decode it yourself by downloading it here.
// Micha� Figlus #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<iostream> #include<fstream> #include<vector> #include<queue> #include<stack> #include<list> #include<algorithm> using namespace std; void update(int k,int x,int *t) { t[x]=k; while(x>1) { x/=2; t[x]=max(t[2*x],t[2*x+1]); } } int maximum(int p,int q,int *t) { int wynik=-2000000000; while(p<=q) { if(wynik<t[p]) wynik=t[p]; if(wynik<t[q]) wynik=t[q]; if(p%2==1) p++; if(q%2==0) q--; p/=2; q/=2; } return wynik; } int main() { int i,j,n,z,w,x1,x2,y1,y2,*p,q,*a,*h; bool b; scanf("%d",&z); for(j=1;j<=z;j++) { scanf("%d%d",&n,&w); vector<pair<int,int> > t; vector<pair<int,int> > v; a = new int [n+1]; h = new int [n+1]; q=1; b=true; while(q<2*n) q*=2; p = new int [q+1]; for(i=1;i<=n;i++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); t.push_back(make_pair(min(x1,x2),i)); h[i]=abs(y2-y1); } for(i=1;i<=n;i++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); v.push_back(make_pair(min(x1,x2),i)); } sort(t.begin(),t.end()); sort(v.begin(),v.end()); for(i=0;i<n;i++) { a[t[i].second]=i; p[q/2+i]=h[t[i].second]; } for(i=q/2+n;i<q;i++) p[i]=0; for(i=q/2-1;i>0;i--) p[i]=max(p[2*i],p[2*i+1]); for(i=0;i<n&&b;i++) { if(a[v[i].second]!=i&&maximum(q/2,q/2+a[v[i].second]-1,p)+h[v[i].second]>w) b=false; else update(0,q/2+a[v[i].second],p); } if(b) printf("TAK\n"); else printf("NIE\n"); } 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 | // Micha� Figlus #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<iostream> #include<fstream> #include<vector> #include<queue> #include<stack> #include<list> #include<algorithm> using namespace std; void update(int k,int x,int *t) { t[x]=k; while(x>1) { x/=2; t[x]=max(t[2*x],t[2*x+1]); } } int maximum(int p,int q,int *t) { int wynik=-2000000000; while(p<=q) { if(wynik<t[p]) wynik=t[p]; if(wynik<t[q]) wynik=t[q]; if(p%2==1) p++; if(q%2==0) q--; p/=2; q/=2; } return wynik; } int main() { int i,j,n,z,w,x1,x2,y1,y2,*p,q,*a,*h; bool b; scanf("%d",&z); for(j=1;j<=z;j++) { scanf("%d%d",&n,&w); vector<pair<int,int> > t; vector<pair<int,int> > v; a = new int [n+1]; h = new int [n+1]; q=1; b=true; while(q<2*n) q*=2; p = new int [q+1]; for(i=1;i<=n;i++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); t.push_back(make_pair(min(x1,x2),i)); h[i]=abs(y2-y1); } for(i=1;i<=n;i++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); v.push_back(make_pair(min(x1,x2),i)); } sort(t.begin(),t.end()); sort(v.begin(),v.end()); for(i=0;i<n;i++) { a[t[i].second]=i; p[q/2+i]=h[t[i].second]; } for(i=q/2+n;i<q;i++) p[i]=0; for(i=q/2-1;i>0;i--) p[i]=max(p[2*i],p[2*i+1]); for(i=0;i<n&&b;i++) { if(a[v[i].second]!=i&&maximum(q/2,q/2+a[v[i].second]-1,p)+h[v[i].second]>w) b=false; else update(0,q/2+a[v[i].second],p); } if(b) printf("TAK\n"); else printf("NIE\n"); } return 0; } |