线段树优化建图,拓扑,没了。
#include <bits/stdc++.h>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define rep(i , j , k) for(int i = j ; i <= k ; i ++)
#define Rep(i , j , k) for(int i = j ; i >= k ; i --)
using namespace std ;
using ll = long long ;
using pii = pair <int , int> ;
using vii = vector <int> ;
// #define int long long
auto ot = [&]() { cerr << "ATS TXDY" << '\n' ; int ATS_nantf_txdy = true ; } ;
auto _ios = [&]() { ios :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ; } ;
namespace stO_ATS_Orz {
template < class T > void cmax(T & x , T y) { if(x < y) x = y ; }
template < class T > void cmin(T & x , T y) { if(x > y) x = y ; }
template < class T > void abs(T x) { if(x < 0) x = -x ; }
int n , s , m ;
const int N = 1e5 + 10 ;
const int M = 2e5 + 10 ;
const int limit = 1e9 ;
struct Edge { int v , nxt , w ; } e[N * 30] ;
int val[N << 3] , d[N << 3] , deg[N << 3] , ls[N << 3] , rs[N << 3] ;
int head[N << 3] , ecnt = 0 , rt , cnt = 0 ;
bool vis[N << 3] ;
void add(int u , int v , int w) { e[++ ecnt] = { v , head[u] , w } ; head[u] = ecnt ; deg[v] ++ ; }
void build(int l , int r , int & p) {
if(l == r) { p = l ; return ; }
p = ++ cnt ; int mid = l + r >> 1 ;
build(l , mid , ls[p]) ; build(mid + 1 , r , rs[p]) ;
add(ls[p] , p , 0) ; add(rs[p] , p , 0) ;
}
void upd(int a , int b , int l , int r , int p , int to) {
if(a <= l && r <= b) { add(p , to, 0) ; return ; }
int mid = l + r >> 1 ;
if(a <= mid) upd(a , b , l , mid , ls[p] , to) ;
if(b > mid) upd(a , b , mid + 1 , r , rs[p] , to) ;
}
void topsort() {
queue < int > q ;
for(int i = 1 ; i <= cnt ; i ++) { if(! d[i]) d[i] = 1 ; if(! deg[i]) q.push(i) ; }
while(q.size()) {
int u = q.front() ; q.pop() ; vis[u] = 1 ;
for(int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ; cmax(d[v] , d[u] + e[i].w) ;
if(val[v] && d[v] > val[v]) { cout << "NIE" << '\n' ; exit(0) ; }
if(! -- deg[v]) q.push(v) ;
}
}
}
void main() {
cin >> n >> s >> m ; cnt = n ; build(1 , n , rt) ;
for(int i = 1 ; i <= s ; i ++) { int pos , _val ; cin >> pos >> _val ; d[pos] = val[pos] = _val ; }
for(int i = 1 ; i <= m ; i ++) {
int l , r , k ; cin >> l >> r >> k ;
int pre = l - 1 , now = 0 ; ++ cnt ;
while(k --) {
cin >> now ;
add(cnt , now , 1) ;
if(now > pre + 1) upd(pre + 1 , now - 1 , 1 , n , rt , cnt) ;
pre = now ;
}
if(now < r) upd(now + 1 , r , 1 , n , rt , cnt) ;
}
topsort() ;
rep(i , 1 , cnt) if(! vis[i] || d[i] > limit) { cout << "NIE" << '\n' ; return ; }
cout << "TAK" << '\n' ;
rep(i , 1 , n) cout << d[i] << ' ' ;
}
}
signed main() {
_ios() ; ot() ;
return stO_ATS_Orz :: main() , 0 ;
}