Submission #893828

#	Time	Username	Problem	Language	Result	Execution time	Memory
893828		The_Blitz	Spiral (BOI16_spiral)	C++17	0 / 100	394 ms	262144 KiB

spiral

// TODO -> PONER ALGO AQUI
// amigos y no más
// I'm in the coolest driver high
// += O(logn) ; + = O(n)
 
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define ones(x) __builtin_popcount(x)
#define loga2(x) __builtin_ctzll(x)
#define pos2(x) __builtin_clzll(x)
using namespace std;
 
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair <ii, ii> iiii;

const ll mod = 1000000007;
const ll inf = (1LL<<62)-1;

long long dp[10005][10005];

// GET VALUE O(1)
long long calc(int x, int y){
  long long z = max( abs(x), abs(y));
  long long lim = ((z+z+1)*(z+z+1))%mod;  
  long long val; 
  // horizontal line
  if(-y == z) val = (mod + mod + lim - (z-x) ) % mod ;
  else{
    lim -= z; lim -= z; lim+=mod; lim+=mod;
    lim %=mod;
    // vertical line
    if(-x == z) val = (mod + mod + lim - (z+y) ) % mod ;
    else{
      lim -= z; lim -= z; lim+=mod; lim+=mod;
      lim %=mod;
      // horizontal line
      if(y == z)  val = (mod + mod + lim - (z+x) ) % mod ;
      else{
        lim -= z; lim -= z; lim+=mod; lim+=mod;
        lim %=mod;
        // vertical line
        if(x == z)  val = (mod + mod + lim - (z-y) ) % mod ;
      }
    }
  }
  return val;
}

void go(){
  int n,q;
  cin>>n>>q;
  for(int i=-5000;i<=5000;i++)
    for(int j=-5000;j<=5000;j++){

      // SUM secondary diagonal and SUBSTRACT PRIMARY DIAGONAL
      dp[i+5001][j+5001]=dp[i+5001][j-1+5001] + dp[i-1+5001][j+5001] -
                         dp[i-1+5001][j-1+5001] + calc(i,j);
      dp[i+5001][j+5001]+=mod;
      dp[i+5001][j+5001]%=mod;
  }

  for(int i=1; i<=q;i++){
    long long x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;

    long long ans = dp[x2+5001][y2+5001] - dp[x2+5001][y1-1+5001] - 
                    dp[x1-1+5001][y2+5001] + dp[x1-1+5001][y1-1+5001];
    ans+= mod ; ans+=mod;
    ans%=mod;
    cout<<ans<<"\n";
  }
} 
    

int main() {
  fastio;
  go();
  return 0;
}

Compilation message (stderr)

spiral.cpp: In function 'long long int calc(int, int)':
spiral.cpp:48:10: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |   return val;
      |          ^~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25