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.
#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define st first #define nd second #define REF & typedef pair<int,int> pii; typedef vector<int> vi; #define REP(i,n) for(int i = 0; i < n; ++i) #define FOR(i,a,b) for(int i = a; i <= b; ++i) #define FORD(i,a,b) for(int i = a; i >= b; --i) template<typename T> class drzewo_przedzialowe_tablicowe{ private: int pot2; // pierwsza pot�ga dw�jki wi�ksza r�wna ni� tab.size() vector<T> drz; // drzewo T (*f)(T,T); // ��czne f T e; // f(e, x) = x public: drzewo_przedzialowe_tablicowe(vector<T> REF tab, T (*__f)(T,T), T __e){ f = __f; e = __e; pot2 = 1; while(pot2 <= tab.size()) pot2 *= 2; drz.resize(2*pot2); REP(i,tab.size()) drz[pot2 + i] = tab[i]; FOR(i,tab.size(),pot2-1) drz[pot2 + i] = e; FORD(i,pot2-1,1) drz[i] = f(drz[2*i], drz[2*i+1]); } void wstaw(T elem, int i){ i += pot2; drz[i] = elem; for(i /= 2; i; i /= 2) drz[i] = f(drz[2*i], drz[2*i+1]); } T zapytanie(int a, int b){ if(a > b) return e; a += pot2; b += pot2; T wynl = e, wynp = e; while(a < b){ if(a & 1) {wynl = f(wynl, drz[a]); ++a;} // je�li a jest prawym dzieckiem if(!(b & 1)) {wynp = f(drz[b], wynp); --b;} // je�li b jest lewym dzieckiem a /= 2; b /= 2; } if(a == b) wynl = f(wynl,drz[a]); return f(wynl, wynp); } }; const int minf = -1000*1000*1000 - 9; int maks(int a, int b){ return max(a,b);} int main(){ int t; scanf("%d", &t); while(t--){ int n, w; scanf("%d%d",&n,&w); vector<pii> a(n), b(n); vi ha(n), hb(n); for(int i = 0; i < n; ++i){ int x1,y1,x2,y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); a[i] = pii(x1,i); ha[i] = abs(y1-y2); } for(int i = 0; i < n; ++i){ int x1,y1,x2,y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); b[i] = pii(x1,i); hb[i] = abs(y1-y2); } //swap(a,b); swap(ha, hb); sort(a.begin(), a.end()); sort(b.begin(), b.end()); //for(int i = 0; i < a.size(); ++i) printf("%d %d\n", a[i].st , a[i].nd); puts("\n"); //for(int i = 0; i < b.size(); ++i) printf("%d %d\n", b[i].st , b[i].nd); puts("\n"); vi p(n); for(int i = 0; i < n; ++i) p[a[i].nd] = i; for(int i = 0; i < n; ++i){ a[i].st = ha[a[i].nd]; b[i].st = hb[b[i].nd]; a[i].nd = p[a[i].nd]; b[i].nd = p[b[i].nd]; } /* printf("%d\n", w); for(int i = 0; i < n; ++i) for(int k = 0; k < n; ++k) if(i < k and b[i].nd < b[k].nd and b[i].st + b[k].st > w) puts("xxxxxxxxxxxxxxxxx"); */ //for(int i = 0; i < a.size(); ++i) printf("%d %d\n", a[i].st , a[i].nd); puts("\n"); // for(int i = 0; i < b.size(); ++i) printf("%d %d\n", b[i].st , b[i].nd); puts("\n"); vector<int> v(n+9, minf); drzewo_przedzialowe_tablicowe<int> d(v, maks, minf); bool fail = 0; for(int i = n; i--;){ int mojeh = b[i].st; int wys = b[i].nd; int maxh = d.zapytanie(0, wys); if(maxh + mojeh > w) { // printf("%d %d %d\n", mojeh, wys, maxh); fail = 1; break; } d.wstaw(mojeh, wys); } puts(fail ? "NIE" : "TAK"); } 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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; #define st first #define nd second #define REF & typedef pair<int,int> pii; typedef vector<int> vi; #define REP(i,n) for(int i = 0; i < n; ++i) #define FOR(i,a,b) for(int i = a; i <= b; ++i) #define FORD(i,a,b) for(int i = a; i >= b; --i) template<typename T> class drzewo_przedzialowe_tablicowe{ private: int pot2; // pierwsza pot�ga dw�jki wi�ksza r�wna ni� tab.size() vector<T> drz; // drzewo T (*f)(T,T); // ��czne f T e; // f(e, x) = x public: drzewo_przedzialowe_tablicowe(vector<T> REF tab, T (*__f)(T,T), T __e){ f = __f; e = __e; pot2 = 1; while(pot2 <= tab.size()) pot2 *= 2; drz.resize(2*pot2); REP(i,tab.size()) drz[pot2 + i] = tab[i]; FOR(i,tab.size(),pot2-1) drz[pot2 + i] = e; FORD(i,pot2-1,1) drz[i] = f(drz[2*i], drz[2*i+1]); } void wstaw(T elem, int i){ i += pot2; drz[i] = elem; for(i /= 2; i; i /= 2) drz[i] = f(drz[2*i], drz[2*i+1]); } T zapytanie(int a, int b){ if(a > b) return e; a += pot2; b += pot2; T wynl = e, wynp = e; while(a < b){ if(a & 1) {wynl = f(wynl, drz[a]); ++a;} // je�li a jest prawym dzieckiem if(!(b & 1)) {wynp = f(drz[b], wynp); --b;} // je�li b jest lewym dzieckiem a /= 2; b /= 2; } if(a == b) wynl = f(wynl,drz[a]); return f(wynl, wynp); } }; const int minf = -1000*1000*1000 - 9; int maks(int a, int b){ return max(a,b);} int main(){ int t; scanf("%d", &t); while(t--){ int n, w; scanf("%d%d",&n,&w); vector<pii> a(n), b(n); vi ha(n), hb(n); for(int i = 0; i < n; ++i){ int x1,y1,x2,y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); a[i] = pii(x1,i); ha[i] = abs(y1-y2); } for(int i = 0; i < n; ++i){ int x1,y1,x2,y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); b[i] = pii(x1,i); hb[i] = abs(y1-y2); } //swap(a,b); swap(ha, hb); sort(a.begin(), a.end()); sort(b.begin(), b.end()); //for(int i = 0; i < a.size(); ++i) printf("%d %d\n", a[i].st , a[i].nd); puts("\n"); //for(int i = 0; i < b.size(); ++i) printf("%d %d\n", b[i].st , b[i].nd); puts("\n"); vi p(n); for(int i = 0; i < n; ++i) p[a[i].nd] = i; for(int i = 0; i < n; ++i){ a[i].st = ha[a[i].nd]; b[i].st = hb[b[i].nd]; a[i].nd = p[a[i].nd]; b[i].nd = p[b[i].nd]; } /* printf("%d\n", w); for(int i = 0; i < n; ++i) for(int k = 0; k < n; ++k) if(i < k and b[i].nd < b[k].nd and b[i].st + b[k].st > w) puts("xxxxxxxxxxxxxxxxx"); */ //for(int i = 0; i < a.size(); ++i) printf("%d %d\n", a[i].st , a[i].nd); puts("\n"); // for(int i = 0; i < b.size(); ++i) printf("%d %d\n", b[i].st , b[i].nd); puts("\n"); vector<int> v(n+9, minf); drzewo_przedzialowe_tablicowe<int> d(v, maks, minf); bool fail = 0; for(int i = n; i--;){ int mojeh = b[i].st; int wys = b[i].nd; int maxh = d.zapytanie(0, wys); if(maxh + mojeh > w) { // printf("%d %d %d\n", mojeh, wys, maxh); fail = 1; break; } d.wstaw(mojeh, wys); } puts(fail ? "NIE" : "TAK"); } return 0; } |