#include<bits/stdc++.h> #define f first #define s second using namespace std; typedef pair<int,int> par; typedef pair<int,par> para; int n, m, tab[1000009], kon[109]; priority_queue<par, vector<par>, greater<par> > q, q1; vector<par> v; int main() { int a,b,c,d=1<<30,e=0; par p; scanf("%d%d", &n, &m); if(m>=n) { printf("TAK"); return 0; } for(int i=1; i<=n; i++) { scanf("%d%d%d", &a, &b, &c); d=min(d,a); e=max(e,b); tab[i]=c; kon[i]=b; q.push(par(a,i)); } for(int i=d; i<=e; i++) { if(!q.empty()) { p=q.top(); while(p.f==i) { a=kon[p.s]; q1.push(par(a,p.s)); q.pop(); if(q.empty()) break; p=q.top(); } } if(!q1.empty()) { v.clear(); for(int j=1; j<=m; j++) { p=q1.top(); if(q1.empty()) break; q1.pop(); tab[p.s]--; if(tab[p.s]>0) v.push_back(p); } for(int j=0; j<v.size(); j++) q1.push(v[j]); p=q1.top(); if(p.first==i) { printf("NIE"); return 0; } } } printf("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 | #include<bits/stdc++.h> #define f first #define s second using namespace std; typedef pair<int,int> par; typedef pair<int,par> para; int n, m, tab[1000009], kon[109]; priority_queue<par, vector<par>, greater<par> > q, q1; vector<par> v; int main() { int a,b,c,d=1<<30,e=0; par p; scanf("%d%d", &n, &m); if(m>=n) { printf("TAK"); return 0; } for(int i=1; i<=n; i++) { scanf("%d%d%d", &a, &b, &c); d=min(d,a); e=max(e,b); tab[i]=c; kon[i]=b; q.push(par(a,i)); } for(int i=d; i<=e; i++) { if(!q.empty()) { p=q.top(); while(p.f==i) { a=kon[p.s]; q1.push(par(a,p.s)); q.pop(); if(q.empty()) break; p=q.top(); } } if(!q1.empty()) { v.clear(); for(int j=1; j<=m; j++) { p=q1.top(); if(q1.empty()) break; q1.pop(); tab[p.s]--; if(tab[p.s]>0) v.push_back(p); } for(int j=0; j<v.size(); j++) q1.push(v[j]); p=q1.top(); if(p.first==i) { printf("NIE"); return 0; } } } printf("TAK"); return 0; } |