Submission #893836

#	Time	Username	Problem	Language	Result	Execution time	Memory
893836		The_Blitz	Spiral (BOI16_spiral)	C++17	27 / 100	55 ms	31824 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[2005][2005];

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

  if(n<=1000){
    for(int i=-1000;i<=1000;i++)
      for(int j=-1000;j<=1000;j++){

        // SUM secondary diagonal and SUBSTRACT PRIMARY DIAGONAL
        dp[i+1001][j+1001]=dp[i+1001][j-1+1001] + dp[i-1+1001][j+1001] -
                           dp[i-1+1001][j-1+1001] + calc(i,j);
        dp[i+1001][j+1001]+=mod;
        dp[i+1001][j+1001]%=mod;
    }
  }
  for(int i=1; i<=q;i++){
    long long x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;

    long long ans;

    if(n<=1000){
      ans = dp[x2+1001][y2+1001] - dp[x2+1001][y1-1+1001] - 
            dp[x1-1+1001][y2+1001] + dp[x1-1+1001][y1-1+1001];
      ans+= mod ; ans+=mod;
      ans%=mod;
      
    }
    else if(x1==x2 and y1==y2){
      ans = calc(x1,y1);
    }
    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: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25