oj.uz

Submission #893836

# Submission time Handle Problem Language Result Execution time Memory
893836 2023-12-27T14:16:19 Z The_Blitz Spiral (BOI16_spiral) C++17
27 / 100
 55 ms 31824 KB 
// 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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31824 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31824 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31824 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -