### non--stop's blog

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

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;
}


• +2

By non--stop, history, 19 months ago,
#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

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)
{
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.

• -37

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

question suggest some approach and reason behind it