non--stop's blog

By non--stop, history, 6 months ago, In English

question

#include <iostream>
#include<math.h>

using namespace std;

int arr[1001][1001];
int dp[1001][1001][4];

int count (int x, int y) {
  return max(min(x,y/2)-1,0)+ max(min(x/2,y)-1,0);
}

int fun(int r, int c) {
  int ans = 0;
  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      for(int k=0;k<4;k++){
        dp[i][j][k] = 0;
      }
    }
  }
  
  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      if(!arr[i][j]) continue;
      dp[i][j][3] = dp[i][j-1][3] + 1;// for left
      dp[i][j][0] = dp[i-1][j][0] + 1;// for top
    }
  }

  for(int i=r;i>=1;i--){
    for(int j=c;j>=1;j--){
      if(!arr[i][j]) continue;
      dp[i][j][1] = dp[i][j+1][1] + 1;// for right
      dp[i][j][2] = dp[i+1][j][2] + 1;// for bottom
    }
  }

  for(int i=1;i<=r;i++){
    for(int j=1;j<=c;j++){
      if(!arr[i][j]) continue;
      // all 4 directions
      ans += count(dp[i][j][0],dp[i][j][1]);// top,right
      ans += count(dp[i][j][1],dp[i][j][2]);//right,bottom
      ans += count(dp[i][j][2],dp[i][j][3]);// bottom,left
      ans += count(dp[i][j][3],dp[i][j][0]);// left, top
    }
  }
  return ans;
}
int main() {
  int  t;
  cin>> t;
  int r,c;
  for(int k=1;k<=t;k++) {
      cin>>r>>c;
      for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
          cin>>arr[i][j];
        }
      }
    cout<<"Case #"<<k<<": "<<fun(r,c)<<"\n";
  }
 return 0;
}  

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By non--stop, history, 19 months ago, In English
#include<bits/stdc++.h>
using namespace std;
 
#define f              first
#define s              second
#define int             long long int
#define pb              push_back
 
// #define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define vvi             vector<vi>
#define vb              vector<bool>
#define vvb             vector<vb>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define rep(i,a,b)      for(int i=a;i<=b;i++)
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
typedef long long ll;
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define MAXN			(int)1e+5
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
struct data {
	int sum;
};
int n, a[MAXN];
data t[4 * MAXN];
data lazy[4 * MAXN];
data combine(data l, data r) {
	data res;
	res.sum = l.sum + r.sum;
	return res;
}
 
data make_data(int val) {
	data res;
	res.sum = val;
	return res;
}
void push(int v, int tl, int tr)
{
	t[v * 2] = combine(t[v * 2], make_data((tr - tl + 1) / 2 * lazy[v].sum));
	t[v * 2 + 1] = combine(t[v * 2 + 1], make_data((tr - tl + 1) / 2 * lazy[v].sum));
	lazy[v * 2] = combine(lazy[v * 2], lazy[v]);
	lazy[v * 2 + 1] = combine(lazy[v * 2 + 1], lazy[v]);
	lazy[v] = make_data(0);
}
// range update a[l...r]
void update(int v, int tl, int tr, int l, int r, int addend)
{
	if (l > r)	return;
	if (l == tl && tr == r) {
		t[v] = combine(t[v], make_data(addend * (tr - tl + 1)));
		if (tl != tr)	lazy[v] = combine(lazy[v], make_data(addend));
	} else {
		push(v, tl, tr);
		int tm = (tl + tr) / 2;
		update(v * 2, tl, tm, l, min(r, tm), addend);
		update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, addend);
		t[v] = combine(t[v * 2], t[v * 2 + 1]);
	}
}
// range query a[l...r]
data query(int v, int tl, int tr, int l, int r) {
	if (l > r)	return make_data(0);
	if (l == tl && r == tr)	return t[v];
	push(v, tl, tr);
	int tm = (tl + tr) / 2;
	return combine(query(v * 2, tl, tm, l, min(r, tm)),
	               query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
int32_t main()
{
	int test;	cin >> test;
	while (test--)
	{
		cin >> n;
		int q;	cin >> q;
		while (q--)
		{
			int op, l, r;	cin >> op >> l >> r;
			if (op == 0)
			{
				int addend;	cin >> addend;
				update(1, 0, n - 1, l - 1, r - 1, addend);
			}
			else if (op == 1)
			cout << query(1, 0, n - 1, l - 1, r - 1).sum << "\n";
		}
	}
	return 0;
} 

it's giving wrong answer on submitting in spoj but working fine in sublime text 3.

Read more »

 
 
 
 
  • Vote: I like it
  • -37
  • Vote: I do not like it

By non--stop, history, 23 months ago, In English

question suggest some approach and reason behind it

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it