Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define ff first
- #define ss second
- #define xd puts("XD")
- #define endl puts("")
- #define ub upper_bound
- #define lb lower_bound
- #define mn 200010
- int n,m,wsk,a,r;
- int stan[mn], ile[mn];
- int zam[1000010];
- int tree[2097300];
- void test_zam()
- {
- for (int i=1; i<=10; i++)
- {
- printf ("i=%d zam[i]=%d\n", i, zam[i]);
- }
- }
- void inserd(int x, int pp, int pk, int zp, int zk)
- {
- if (pk<zp || zk<pp)
- {
- return;
- }
- if (zp<=pp && pk<=zk)
- {
- tree[x]++;
- return;
- }
- int sr=(pp+pk)/2;
- inserd(2*x, pp, sr, zp, zk);
- inserd(2*x+1, sr+1, pk, zp, zk);
- }
- int main()
- {
- scanf ("%d%d", &n, &m);
- r=1;
- while (r<1000000)
- {
- r*=2;
- }
- for (int i=1; i<=n; i++)
- {
- scanf ("%d", &stan[i]);
- stan[i]*=-1;
- }
- //xd;
- for (int i=1; i<=m; i++)
- {
- scanf ("%d", &a);
- inserd (1, 1, r, 1, a);
- }
- for (int i=r; i-r+1<=1000000; i++)
- {
- int x=i;
- while (x>0)
- {
- zam[i-r+1]+=tree[x];
- ile[i-r+1]+=tree[x];
- x/=2;
- }
- }
- sort (stan+1, stan+1+n);
- for (int i=1; i<=n; i++)
- {
- stan[i]*=-1;
- }
- //test_zam();
- wsk=1;
- for (int i=1; i<=1000000; i++)
- {
- //printf ("i=%d zam[i]=%d ile[i]=%d\n", i, zam[i], ile[i]);
- while (stan[wsk]<zam[i])
- {
- //printf ("PETLA wsk=%d stan[wsk]=%d\n", wsk, stan[wsk]);
- zam[i]-=stan[wsk];
- wsk++;
- //printf ("zam[i]=%d wsk=%d\n", zam[i], wsk);
- if (wsk>n)
- {
- puts ("NIE");
- return 0;
- }
- }
- stan[wsk]-=zam[i];
- stan[wsk]=min(stan[wsk], ile[i]-zam[i]);
- //printf ("wsk=%d stan[wsk]=%d\n", wsk, stan[wsk]);
- }
- puts ("TAK");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement