Submission #993751

#	Time	Username	Problem	Language	Result	Execution time	Memory
993751		samek08	Furniture (JOI20_furniture)	C++14	0 / 100	2 ms	3676 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace std;
//using namespace __gnu_pbds;
//template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = 1005, base = (1<<10), rozmiar_drzewa = base * 2, INF = 2e9+50;
const ll INF_L = (ll)1e18+(ll)50000;

int n,m,q,y,x;
bool A[MAXN][MAXN];
vector<int> tree[MAXN];
int wsk[MAXN];
set<int> S[MAXN];
int G[MAXN][MAXN];

void update(int i, int v, int val)
{
	v += base, tree[i][v] += val, v /= 2;
	while(v > 0) tree[i][v] = tree[i][v*2] + tree[i][v*2+1], v /= 2;
}

int query(int i, int l, int p)
{
	l = l + base - 1, p = p + base + 1;
	int res = 0;
	while(l/2 != p/2)
	{
		if(l % 2 == 0) res += tree[i][l+1];
		if(p % 2 == 1) res += tree[i][p-1];
		l /= 2, p /= 2;
	}
	return res;
}

bool dodaj(int y, int x)
{
	if(x <= wsk[y]) return 1;
	if(n == 1 or m == 1) return 0;

	bool stan = 1;
	if(y == 1) stan = 0;
	else
	{
		int idx = min(m,x+1);
		if(S[y-1].empty()) stan = 1;
		else if(*S[y-1].begin() > idx) stan = 1;
		else
		{
			if(*S[y-1].rbegin() <= idx) stan = G[y-1][*S[y-1].rbegin()];
			else
			{
				auto it = S[y-1].lower_bound(idx);
				if(*it > idx) --it;
				stan = G[y-1][*it];
			}
			//cout << "YY: " << y << " XX: " << x << " STAN: " << stan << endl;
		}
	}

	//cout << "Y: " << y << " X: " << x << " STAN: " << stan << endl;

	G[y][x] = stan;

	if(y == n)
	{
		if(stan == 0) return 0;
		else
		{
			S[y].insert(x), wsk[y] = x;
			return 1;
		}
	}
	else
	{
		if(x > wsk[y+1]+1)
		{
			S[y].insert(x), update(y,x,1);
			return 1;
		}
		else
		{
			if(stan == 1)
			{
				if(x == m or query(y,x+1,m) == m-x) return 0;
				else
				{
					S[y].insert(x), wsk[y] = x, update(y,x,1);
					return 1;
				}
			}
			return 0;
		}
	}
}

void solve()
{
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) cin >> A[i][j];

	for(int i = 1; i <= n; ++i) tree[i].assign(rozmiar_drzewa,0), wsk[i] = 0;

	for(int i = 1; i <= n; ++i) S[i].insert(0), G[i][0] = 1;
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= m; ++j)
		{
			if(A[i][j] == 1)
			{
				bool val = dodaj(i,j);
			}
		}
	}

	cin >> q;
	while(q--)
	{
		cin >> y >> x;

		bool val = dodaj(y,x);
		if(val) cout << "1" << '\n';
		else cout << "0" << '\n';
	}
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
   	//cin >> T;
    while(T--) solve();

    return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'void solve()':
furniture.cpp:118:10: warning: unused variable 'val' [-Wunused-variable]
  118 |     bool val = dodaj(i,j);
      |          ^~~

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