oj.uz

Submission #764482

# Submission time Handle Problem Language Result Execution time Memory
764482 2023-06-23T12:47:18 Z Ellinor Spiral (BOI16_spiral) C++14
27 / 100
 1500 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i = (a); i < (b); i++)
typedef long long ll;

ll N,q;//
ll mod = 1e9 + 7;

ll coor(ll x1, ll y1)
{
    ll circle = max(abs(x1),abs(y1));
    ll root = circle*2;
    root++;
    ll square = root*root;
    
    ll ans;
    if(y1==(-circle)){
        ll diff = circle - x1;
        ans = square - diff;
    }
    else if(x1==(-circle)){
        ll diff = circle + y1;
        diff += circle;
        diff += circle;
        ans = square - diff;
    }
    else if(y1==circle){
        ll diff = circle*4;
        diff += circle + x1;
        ans = square - diff;
    }
    else{
        ll diff = circle*6;
        diff += (circle - y1);
        ans = square - diff;
    }
    ans = ans % mod;

    return ans;
}

vector<vector<ll>> segtrees;

ll low, high;
ll segtree_i;

ll query(ll node, ll my_low, ll my_high)
{
    if (low <= my_low && my_high <= high) return segtrees[segtree_i][node];
    if (my_low >= high || my_high <= low) return 0;

    return query(node*2, my_low, (my_low + my_high)/2) + query(node*2+1, (my_low + my_high)/2, my_high);
}

int32_t main()
{
    cin>>N>>q;

    ll nn;
    ll conv;
    ll xl = N*2; //x length
    xl++;

    if (N<=1e5)
    {
        nn=1;
        while(nn<xl) nn<<=1;

        segtrees.assign(xl, vector<ll>(nn*2, 0)); // summa

        conv = N;

        rep(i,0,xl){
            rep(j,0,xl){
                segtrees[i][nn + j] = coor(j - conv, i - conv);
            }

            for(ll j = nn-1; j>0; j--){
                segtrees[i][j] = segtrees[i][j*2] + segtrees[i][j*2+1];
                segtrees[i][j] = segtrees[i][j] % mod;
            }
        }
    }

    // rep(i,0,segtrees[4].size()){
    //     cerr << segtrees[4][i] << " ";
    // }
    // cerr<<"\n";

    ll x1, y1, x2, y2;
    rep(i,0,q)
    {
        cin>>x1>>y1>>x2>>y2;

        if(x1==x2 && y1==y2) cout<< coor(x1, y1) <<"\n";

        else
        {
            ll ans = 0;
            low = x1 + conv;
            high = x2 + conv + 1;
            rep(j, y1, y2 + 1)
            {
                segtree_i = j + conv;
                ans +=  query(1, 0, nn);
                ans = ans % mod;
            }

            cout<<ans<<"\n";
        }

    }
}

Compilation message

spiral.cpp: In function 'int32_t main()':
spiral.cpp:61:8: warning: 'conv' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     ll conv;
      |        ^~~~
spiral.cpp:106:30: warning: 'nn' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |                 ans +=  query(1, 0, nn);
      |                         ~~~~~^~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 64548 KB Output is correct
2 Runtime error 97 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1556 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 64548 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 97 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -