Submission #506365

#	Time	Username	Problem	Language	Result	Execution time	Memory
506365		fcmalkcin	Furniture (JOI20_furniture)	C++17	100 / 100	533 ms	60000 KiB

furniture

/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>
using namespace std;

#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define For(i,a,b) for (ll i=a;i<=b;i++)

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e3+200;
const ll mod=1e9+7  ;
const ll base=3e18;

/// you will be the best but now you just are trash
/// goal 3/7

ll cnt[maxn][maxn];
ll cnt1[maxn][maxn];
bool dd[maxn][maxn];
ll ax[5]= {0,1,0,-1};
ll ay[5]= {1,0,-1,0};
ll fwt[maxn][maxn][2];
ll a[maxn][maxn];
ll n, m;

void update(ll x,ll y,ll t,ll diff)
{
    ll len=(t==0?m:n);
    for (int i=y; i<=len; i+= i&(-i))
    {
        fwt[x][i][t]+=diff;
    }
}
ll get(ll x,ll l,ll r,ll t)
{
    ll ans=0;
    for (int i=r;i;i-= i&(-i))
    {
        ans+=fwt[x][i][t];
    }
     for (int i=l-1;i;i-= i&(-i))
    {
        ans-=fwt[x][i][t];
    }
    return ans;
}
void add(ll x,ll y)
{
    if (dd[x][y]) return ;
    queue<pll> q;
    q.push(make_pair(x,y));
    dd[x][y]=1;
    while (!q.empty())
    {
        auto p=q.front();
        q.pop();
        ll x=p.ff;
        ll y=p.ss;
        update(x,y,0,-1);
        update(y,x,1,-1);
        bool chk=(make_pair(x,y)==make_pair(1ll,3ll));
        for (int t=0; t<4; t++)
        {
            ll x1=x+ax[t];
            ll y1=y+ay[t];
            if (x1>=1&&x1<=n&&y1>=1&&y1<=m&&!dd[x1][y1])
            {
                if (t<=1)
                {
                    cnt[x1][y1]--;
                    if (!cnt[x1][y1])
                    {
                        dd[x1][y1]=true;
                        q.push(make_pair(x1,y1));
                    }
                }
                else
                {
                    cnt1[x1][y1]--;
                    if (!cnt1[x1][y1])
                    {
                        dd[x1][y1]=true;
                        q.push(make_pair(x1,y1));
                    }
                }
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin>> n>> m;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            cin>>a[i][j];
            for (int t=0; t<4; t++)
            {
                ll x1=i+ax[t];
                ll y1=j+ay[t];
                if (x1>=1&&x1<=n&&y1>=1&&y1<=m)
                {
                    if (t<=1)
                    {
                        cnt1[i][j]++;
                    }
                    else
                    {
                        cnt[i][j]++;
                    }
                }
            }
            update(i,j,0,1);
            update(j,i,1,1);
        }
    }

     for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (a[i][j]==1)
            {
                add(i,j);
            }
        }
    }
   /*  for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            cout <<dd[i][j]<<" ";
        }
        cout <<endl;
    }*/
    ll q;
    cin>> q;
    while (q--)
    {
        ll x, y;
        cin>>x>> y;
        bool chk=false;
        if (x+1<=n&&y>=2&&get(x+1,1,y-1,0))
        {
            chk=true;
        }
         if (y+1<=m&&x>=2&&get(y+1,1,x-1,1))
        {
            chk=true;
        }
        if (chk)
        {
            add(x,y);
        }
        cout <<chk<<endl;
    }
}

Compilation message (stderr)

furniture.cpp: In function 'void add(long long int, long long int)':
furniture.cpp:69:14: warning: unused variable 'chk' [-Wunused-variable]
   69 |         bool chk=(make_pair(x,y)==make_pair(1ll,3ll));
      |              ^~~
furniture.cpp: In function 'int main()':
furniture.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95