[CF] Counting Rectangles

https://codeforces.com/contest/1722/problem/E

Problem - E - Codeforces

문제 제목 그대로 가로, 세로가 정해진 여러 직사각형들이 주어지고, h_s < h_i < h_b && w_s < w_i < w_b인 직사각형들의 넓이 합을 구해야 한다.

 

2차원 누적합을 이용해 해결하면 된다. 2차원이므로 포함과 배제 느낌으로 누적합 배열을 채워주면 된다.

 

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

ll n, q;
ll p[1005][1005];
ll a[1005][1005];

void solve()
{
    memset(a, 0, sizeof(a));
    memset(p, 0, sizeof(p));
    cin>>n>>q;
    for(ll i=0;i<n;i++)
    {
        ll h, w; cin>>h>>w;
        a[h][w]+=h*w;
    }
    for(ll i=1;i<=1000;i++) for(ll j=1;j<=1000;j++) 
        p[i][j]=a[i][j]+p[i-1][j]+p[i][j-1]-p[i-1][j-1];
    while(q--)
    {
        ll hs, ws, hb, wb; cin>>hs>>ws>>hb>>wb;
        hb--; wb--;
        cout<<p[hb][wb]-p[hs][wb]-p[hb][ws]+p[hs][ws]<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1; cin>>tc;
    while(tc--) solve();
    return 0;
}