题目描述
// 写死我了…二分加3维前缀和差点就过不了,时间卡的真的紧
样例
#include <iostream>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N = 3e2 + 10,M = 2e6 + 10;
struct node{
int al,ar,bl,br,kl,kr;
ll c;
};
node state[M];
ll arr[M];
ll sum[M];
int a,b,c,m;
int root;
inline int pos(int ua,int ub,int uc)
{
return ((ua - 1) * b + ub - 1) * c + uc;
}
bool check(int u)
{
memset(sum,0,sizeof sum);
ll x;
ll p = 1;
bool t = true;
if(root > u){
t = false;
swap(root,u);
p = -1;
}
for(register int i = root + 1;i <= u;i ++)
{
node& h = state[i];
x = p * h.c;
//cout << h.c << endl;
arr[pos(h.al,h.bl,h.kl)] += x;
arr[pos(h.ar+1,h.bl,h.kl)] -= x;
arr[pos(h.al,h.bl,h.kr + 1)] -= x;
arr[pos(h.al,h.br + 1,h.kl)] -= x;
arr[pos(h.ar + 1,h.br + 1,h.kl)] += x;
arr[pos(h.ar + 1,h.bl,h.kr + 1)] += x;
arr[pos(h.al,h.br + 1,h.kr + 1)] += x;
arr[pos(h.ar + 1,h.br + 1,h.kr + 1)] -= x;
}
if(t)root = u;
//cout << root << ' ' << u << endl;
//cout << u << ":@ ";
for(register int i = 1;i <= a;i ++)
{
for(register int j = 1;j <= b;j ++)
{
for(register int k = 1;k <= c;k ++)
{
sum[pos(i,j,k)] = (sum[pos(i,j,k-1)] + sum[pos(i,j-1,k)] + sum[pos(i-1,j,k)]) - (sum[pos(i-1,j-1,k)] +
sum[pos(i-1,j,k-1)] + sum[pos(i,j-1,k-1)]) + sum[pos(i-1,j-1,k-1)] + arr[pos(i,j,k)];
//cout << sum[pos(i,j,k)] << ' ';
if(sum[pos(i,j,k)] < 0)return false;
}
}
}
//cout << endl;
return true;
}
int main()
{
cin >> a >> b >> c >> m;
//cout << pos(1,1,1) << endl;
ll x;
for(register int i = 1;i <= a;i ++)
{
for(register int j = 1;j <= b;j ++)
{
for(register int k = 1;k <= c;k ++)
{
scanf("%d",&x);
arr[pos(i,j,k)] += x;
arr[pos(i,j,k + 1)] -= x;
arr[pos(i,j + 1,k)] -= x;
arr[pos(i + 1,j,k)] -= x;
arr[pos(i + 1,j + 1,k)] += x;
arr[pos(i + 1,j,k + 1)] += x;
arr[pos(i,j + 1,k + 1)] += x;
arr[pos(i + 1,j + 1,k + 1)] -= x;
}
}
}
int ans = 0;
for(register int i = 1;i <= m;i ++)
{
scanf("%d%d%d%d%d%d%lld",&state[i].al,&state[i].ar,&state[i].bl,&state[i].br,&state[i].kl,&state[i].kr,&state[i].c);
state[i].c = -state[i].c;
}
int l = 0,r = m;
//cout << check(2) << endl;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(check(mid))l = mid;
else r = mid - 1;
}
//cout << endl;
cout << (r + 1) << endl;
}
/*
20 20 1 3
257 1157 1623 1296 1172 890 208 987 1547 1096 465 522 1286 1809 1406 1788 773 1065 701 520 1436 212 1026 878 1313 719 897 1395 1241 1996 412 1742 272 1096 870 1981 1778 866 396 1288 1593 507 349 900 401 220 1326 511 703 1058 1005 681 648 1188 1708 1377 1133 1308 1251 1386 1474 734 926 1086 1279 1269 1366 930 1165 1594 660 1515 629 395 1019 200 366 1208 1023 1009 1308 312 1930 1708 1698 889 549 1547 440 1134 764 1522 1103 1752 1933 1272 1149 218 386 1101 682 598 966 1334 956 727 704 1957 1481 1255 1253 485 1680 1297 622 1556 1855 1143 1310 1516 1716 730 1141 1165 1964 1309 1088 1085 1144 1720 1549 780 850 242 673 1211 837 1236 1897 1212 899 1068 803 1851 712 443 1196 655 1592 1236 754 208 996 1526 870 611 1767 1835 1508 649 1971 1112 1010 598 1049 1096 1332 283 976 1927 1506 787 539 354 1618 1464 656 1545 619 428 1197 1076 414 1871 1497 404 1945 952 341 663 1116 1232 1936 1435 771 425 1139 756 235 743 241 1453 442 1194 775 1450 1069 238 1088 329 1527 287 1199 1715 1088 1732 1484 873 669 403 1092 1241 934 912 1243 1181 1091 1532 1917 1091 1592 1553 1836 1082 641 1933 1277 841 915 1546 1709 941 1375 542 618 933 868 1339 786 1938 1281 433 1269 1461 1983 1148 1286 829 585 365 468 1603 1665 221 804 591 1258 1785 281 1874 1380 943 599 1527 276 1923 1730 1128 543 1311 382 1998 1734 505 1179 225 1060 1561 1266 499 1558 906 291 1031 1375 1362 1594 1159 1255 421 1549 1928 342 1669 1669 1777 1703 301 1263 1736 979 967 927 1147 664 1046 1115 967 1838 1289 1886 208 780 477 596 337 1980 1529 1245 448 1982 683 431 972 1074 928 1168 1072 793 1879 1329 1600 743 623 1770 892 894 966 666 1073 1068 863 1088 1329 1076 1929 1582 1793 336 1056 435 1220 567 240 745 232 1643 1996 1977 1456 356 1356 1750 1261 1961 822 1159 1708 1349 243 1617 1616 532 594 279 1483 545 1639 709 575 1278 1126 1929 1860 906 1105 1630 325 587 635
12 19 3 8 1 1 20
2 3 4 13 1 1 18
14 19 4 13 1 1 26*/
为啥是要M = 2e6 + 10这么大的,1e6+10为啥就wa了?? 感觉没超过啊
辛苦啦,给你揉揉QAQ
蟹蟹,QWQ