#define make_pair mp #define emplace_back pb #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5, K = 1e6 + 5; int n, m, k; map<int, int> mapaG, mapaD; set<int> row[N], col[N]; void addD(int x, int y) { auto it = mapaD.upper_bound(x); it--; if(it -> second >= y) return; it++; while(it != mapaD.end() && it -> second <= y) { auto it2 = it; it++; mapaD.erase(it2); } mapaD[x] = y; if(x >= 0 && x < n) { auto it = row[x].upper_bound(y); if(it != row[x].begin()) { it--; addD(x - 1, *it + 1); } } if(y >= 0 && y < m) { auto it = col[y].lower_bound(x); if(it != col[y].end()) addD(*it - 1, y + 1); } } bool checkD(int x, int y) { auto it = mapaD.upper_bound(x); it--; return it -> second >= y; } void addG(int x, int y) { auto it = mapaG.lower_bound(x); if(it -> second <= y) return; it--; while(it != mapaG.end() && it -> second >= y) { auto it2 = it; it--; mapaG.erase(it2); } mapaG[x] = y; if(x >= 0 && x < n) { auto it = row[x].lower_bound(y); if(it != row[x].end()) { addG(x + 1, *it - 1); } } if(y >= 0 && y < m) { auto it = col[y].upper_bound(x); if(it != col[y].begin()) { it--; addG(*it + 1, y - 1); } } } bool checkG(int x, int y) { auto it = mapaG.lower_bound(x); return it -> second <= y; } int main() { scanf("%d%d%d", &n, &m, &k); mapaD[-1] = -5; for(int i=0;i<n-1;i++) mapaD[i] = 0; mapaD[n - 1] = m + 5; mapaG[0] = -5; for(int i=1;i<=n-1;i++) mapaG[i] = m-1; mapaG[n] = m + 5; int x = 0, r, c, z; for(int i=1;i<=k;i++) { scanf("%d%d%d", &r, &c, &z); r = (r ^ x) % n; c = (c ^ x) % m; //cout<<r<<" "<<c<<endl; if(checkD(r, c) && checkG(r, c)) { printf("TAK\n"); x = x ^ z; } else { printf("NIE\n"); col[c].insert(r); row[r].insert(c); if(checkD(r, c)) addD(r - 1, c + 1); if(checkG(r, c)) addG(r + 1, c - 1); } /*cout<<"MapaG :"<<endl; for(auto it : mapaG) cout<<it.first<<" "<<it.second<<endl; cout<<"Koniec Mapy"<<endl;*/ } 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 | #define make_pair mp #define emplace_back pb #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5, K = 1e6 + 5; int n, m, k; map<int, int> mapaG, mapaD; set<int> row[N], col[N]; void addD(int x, int y) { auto it = mapaD.upper_bound(x); it--; if(it -> second >= y) return; it++; while(it != mapaD.end() && it -> second <= y) { auto it2 = it; it++; mapaD.erase(it2); } mapaD[x] = y; if(x >= 0 && x < n) { auto it = row[x].upper_bound(y); if(it != row[x].begin()) { it--; addD(x - 1, *it + 1); } } if(y >= 0 && y < m) { auto it = col[y].lower_bound(x); if(it != col[y].end()) addD(*it - 1, y + 1); } } bool checkD(int x, int y) { auto it = mapaD.upper_bound(x); it--; return it -> second >= y; } void addG(int x, int y) { auto it = mapaG.lower_bound(x); if(it -> second <= y) return; it--; while(it != mapaG.end() && it -> second >= y) { auto it2 = it; it--; mapaG.erase(it2); } mapaG[x] = y; if(x >= 0 && x < n) { auto it = row[x].lower_bound(y); if(it != row[x].end()) { addG(x + 1, *it - 1); } } if(y >= 0 && y < m) { auto it = col[y].upper_bound(x); if(it != col[y].begin()) { it--; addG(*it + 1, y - 1); } } } bool checkG(int x, int y) { auto it = mapaG.lower_bound(x); return it -> second <= y; } int main() { scanf("%d%d%d", &n, &m, &k); mapaD[-1] = -5; for(int i=0;i<n-1;i++) mapaD[i] = 0; mapaD[n - 1] = m + 5; mapaG[0] = -5; for(int i=1;i<=n-1;i++) mapaG[i] = m-1; mapaG[n] = m + 5; int x = 0, r, c, z; for(int i=1;i<=k;i++) { scanf("%d%d%d", &r, &c, &z); r = (r ^ x) % n; c = (c ^ x) % m; //cout<<r<<" "<<c<<endl; if(checkD(r, c) && checkG(r, c)) { printf("TAK\n"); x = x ^ z; } else { printf("NIE\n"); col[c].insert(r); row[r].insert(c); if(checkD(r, c)) addD(r - 1, c + 1); if(checkG(r, c)) addG(r + 1, c - 1); } /*cout<<"MapaG :"<<endl; for(auto it : mapaG) cout<<it.first<<" "<<it.second<<endl; cout<<"Koniec Mapy"<<endl;*/ } return 0; } |