Diamond Queries
National Olympiad — National round (2009 season)
Submission name: diamonds.cpp
Problem summary
A rectangular deposit has L×M×N unit cubes containing known nonnegative carat amounts. For each axis-aligned query box return the total carats inside it.
Input
L M N, then L·M·N values ordered with x varying fastest, then y, then z. Remaining lines until EOF contain x1 y1 z1 x2 y2 z2.
Output
One total per query.
Constraints
1 ≤ L,M,N ≤ 100; each cube contains 0..2000 carats; at most 500000 queries; 0 ≤ x1 < x2 ≤ L and similarly for y,z.
Worked example
An independently prepared example for this explanation.
Input
3 3 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 0 0 3 3 2 1 0 1 3 2 2
Output
171 52
Solution analysis
- Store P[x,y,z], the sum of cubes with coordinates below x,y,z. Use an extra zero layer on each axis. Build it using three positive face-prefix terms, three negative edge-prefix terms, and one positive corner term.
- A query covers half-open ranges [x1,x2), [y1,y2), [z1,z2). Inclusion–exclusion combines the eight prefix corners, using a positive sign for an even number of lower endpoints and a negative sign for an odd number.
- The full sample box contains numbers 1 through 18, totaling 171. The smaller box selects values 11,12,14,15 and returns 52. Each query needs only eight lookups regardless of its volume.
Why it works
The prefix recurrence adds the three face prefixes; pairwise overlaps are subtracted and their common overlap restored, leaving every earlier cube once plus the current cube. Applying the same inclusion–exclusion principle to the lower bounds removes exactly the cubes outside the query.
Watch out. The input order is z outermost and x innermost. Read queries to EOF. Signed 64-bit sums make intermediate inclusion–exclusion safe.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
// Compute the exact archive answer using the method explained above.
ios::sync_with_stdio(false);
cin.tie(nullptr);
int l,m,n;
cin>>l>>m>>n;
vector<long long>prefix(static_cast<size_t>(l+1)*(m+1)*(n+1),0);
auto at=[&](int x,int y,int z)->long long&{
return prefix[(static_cast<size_t>(z)*(m+1)+y)*(l+1)+x];
};
for(int z=1;z<=n;z++){
for(int y=1;y<=m;y++){
for(int x=1;x<=l;x++){
long long value;
cin>>value;
at(x,y,z)=value+at(x-1,y,z)+at(x,y-1,z)+at(x,y,z-1)-
at(x-1,y-1,z)-at(x-1,y,z-1)-at(x,y-1,z-1)+at(x-1,y-1,z-1);
}
}
}
int x1,y1,z1,x2,y2,z2;
while(cin>>x1>>y1>>z1>>x2>>y2>>z2){
long long answer=at(x2,y2,z2)-at(x1,y2,z2)-at(x2,y1,z2)-at(x2,y2,z1)+at(x1,y1,z2)+
at(x1,y2,z1)+at(x2,y1,z1)-at(x1,y1,z1);
cout<<answer<<'\n';
}
}