제출 #1293772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293772		trantrungkein	Spiral (BOI16_spiral)	C++20	12 / 100	137 ms	157252 KiB

spiral

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[2005][2005],pre[2005][2005],vis[2005][2005];
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};
const int Mod = 1e9 + 7;

namespace sub1{
    bool ok(int u, int v){
        if(1 <= u && u <= 2*n+1 && 1 <= v && v <= 2*n+1) {
            if(vis[u][v] == 1) return 0;
            return 1;
        }
        return false;
    }
    vector<pair<int,int>> vec;
    void solve(){
        pair<int,int> st = {2*n+1,2*n+1};
        int id = 0;
        vis[2*n+1][2*n+1] = 1;

        vec.push_back({2*n+1,2*n+1});
        pair<int,int> base = {n+1,n+1};
        while(st != base){
            int u = st.first + dx[id] , v = st.second + dy[id];
            if(!ok(u,v)) {
                id++; if(id > 3) id = 0;
                continue;
            }
            vis[u][v] = 1;
            st = {u,v};
            vec.push_back({u,v});
        }
        int num = (2*n+1)*(2*n+1);
      //  reverse(vec.begin(),vec.end());
        for(auto [x,y] : vec){
           // cout << x <<' ' << y << endl;
            a[x][y] = num;
            num--;
        }
        for(int i = 1; i <= 2*n+1; i++)
        for(int j = 1; j <= 2*n+1; j++){
         //   cout << a[i][j] <<' '; if(j == 2*n+1) cout <<'\n';
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
        }
        cout <<endl;
        while(q--){
            int u,v,x,y;
            cin >> u >> v >> x >> y;
            swap(u,v); swap(x,y);
            u = -u; x = -x;
            u += n + 1; v += n+1, x += n + 1, y += n+1;
            int l = max(u,x), r = max(v,y), a = min(u,x), b = min(v,y);
           // cout << a <<' ' << b <<' ' << l <<' ' <<r << endl;
            cout << (pre[l][r] - pre[l][b-1] - pre[a-1][r] + pre[a-1][b-1])%Mod <<'\n';
        }
    }
}
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    if(n <= 1000) return sub1::solve(),0;
}

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