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
| #include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #define ll long long using namespace std; inline ll read(){ ll res=0,f=1;char ch=getchar(); while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f; } inline void write(ll x){ if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else{ write(x/10); putchar(x%10+'0'); } } ll n,ans[2000010],a[2000010],tmp[2000010]; ll p[2000010],d[2000010],sum[2000010],f[2000010][20]; void ST(){ for(ll j=1;(1<<j)<=n*2;j++){ for(ll i=1;i+(1<<j)-1<=n*2;i++){ f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } } ll RMQ(ll l,ll r){ ll k=0; while((1<<(k+1))<=r-l+1) k++; return min(f[l][k],f[r-(1<<k)+1][k]); } int main(){ n=read(); for(ll i=1;i<=n;i++) p[i]=read(),d[i]=read(); sum[0]=0; memset(f,63,sizeof(f)); for(ll i=1;i<=n*2;i++){ sum[i]=sum[i-1]+(p[i]-d[i]); } for(ll i=1;i<=n*2;i++){ f[i][0]=sum[i]; } ST(); for(ll i=1;i<=n;i++){ ll qx=RMQ(i,i+n-1); if(qx>=sum[i-1]) ans[i]=1; } memcpy(tmp,p,sizeof(p)); for(ll i=1;i<=n;i++) p[i]=tmp[n-i+1]; memcpy(tmp,d,sizeof(d)); for(ll i=1;i<=n;i++) d[i]=tmp[n-i];d[n]=tmp[n]; sum[0]=0; memset(f,63,sizeof(f)); for(ll i=1;i<=n*2;i++){ sum[i]=sum[i-1]+(p[i]-d[i]); } for(ll i=1;i<=n*2;i++){ f[i][0]=sum[i]; } ST(); for(ll i=1;i<=n;i++){ ll qx=RMQ(i,i+n-1); if(qx>=sum[i-1]) ans[n-i+1]=1; } for(ll i=1;i<=n;i++){ if(ans[i]==1) puts("TAK"); else puts("NIE"); } return 0; }
|