求卡常（悬关）
- 板块P3437 [POI2006] TET-Tetris 3D
- 楼主EricWan
- 当前回复3
- 已保存回复3
- 发布时间2024/3/15 21:25
- 上次更新2024/3/16 06:21:24
查看原帖
被骇客银狼阻止的越权访问保存失败
求卡常（悬关）
疑似调用过多，但我感觉能加的优化都加了，56 分。
// Problem: P3437 [POI2006] TET-Tetris 3D
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3437
// Memory Limit: 125 MB
// Time Limit: 1500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
//#include <bits/extc++.h>
// #define min(x,y) (((x)<(y))?(x):(y))
// #define max(x,y) (((x)>(y))?(x):(y))
#define lowbit(x) ((x)&-(x))
#define abs(x) (((x)<(0))?(-(x)):(x))
#define swap(a,b) a^=b^=a^=b
#define INF 1e18
#define MAXN 6000005
#define pushup(id) maxn[id] = max(maxn[id], max(maxn[(id << 2) + 1], max(max(maxn[(id << 2) + 2], maxn[(id << 2) + 3]), maxn[(id << 2) + 4])));
#define pushdown(id) if (tag[id] != 0) { \
tag[(id << 2) + 1] = maxn[(id << 2) + 1] = tag[(id << 2) + 2] = maxn[(id << 2) + 2] = tag[(id << 2) + 3] = maxn[(id << 2) + 3] = tag[(id << 2) + 4] = maxn[(id << 2) + 4] = tag[id]; \
tag[id] = 0; \
}
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
namespace fast_io {
#define MAX_OUTPUT 10000000
char ch,a[MAX_OUTPUT],*p=a,*l=a,sep=' ';//a:buffer area of speed output p:the head of the queue l:the tail of the queue sep:the sperator of vector output
#define def_scan_int(A) inline void scan(A&x){x=0;do{ch=getchar();}while(ch<48||ch>57);while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}} //scan integer
#if 0 //0:normal output 1:speed output(need flush() after output)
#define printc(A) *(p++)=A //speed char output
#define prints(A,B) memcpy(p,A,B) //speed char[] output
#else
#define printc(A) putchar(A) //normal char output
#define prints(A,B) for(register int i=0;i<B;i++){putchar(A[i]);} //speed char[] output
#endif
#define def_print_int(A) void print(const A x){if(9<x){print(x/10);}printc(x%10|48);} //print integer
def_scan_int(short); //scan short
def_scan_int(signed); //scan int
def_scan_int(long long); //scan long long
def_scan_int(__int128); //scan __int128
inline void scan(register char&x){do{x=getchar();}while(x<=32);} //scan char
inline void scan(register char*x){do{ch=getchar();}while(ch<=32);while(ch>32){*(x++)=ch;ch=getchar();}} //scan char*
inline void scan(string&x){do{ch=getchar();}while(ch<=32);while(ch>32){x.push_back(ch);ch=getchar();}} //scan string
template<typename T>
inline void scan(vector<T>&x){for(register auto&it:x){scan(it);}} //scan vector<T>
inline void read(){} //read(a)={scan(a);read();}
template<typename T,typename...arg>
inline void read(register T&x,arg&...oth){scan(x);read(oth...);} //read(a,b,c,d,e)={scan(a);read(b,c,d,e);}
def_print_int(short); //print short
def_print_int(signed); //print int
def_print_int(long long); //print long long
def_print_int(__int128); //print __int128
inline void print(const char x){printc(x);} //print char
inline void print(const char*x){prints(x,strlen(x));} //print char*
inline void print(const string x){prints(x,x.size());} //print string
template<typename T>
inline void print(const vector<T>x){for(auto&it:x){print(it);putchar(sep);}} //print vector<T>
inline void write(){} //write(a)={print(a);write();}
template<typename T,typename...arg>
inline void write(const T x,const arg...oth){print(x);write(oth...);} //write(a,b,c,d,e)={print(a);write(b,c,d,e);}
inline void flush(){fwrite(l,1,p-l,stdout);l=p;} //flush the queue to the console,clear the queue
}
#define read fast_io::read
#define write fast_io::write
#define sep fast_io::sep
#define flush fast_io::flush
unsigned int log2_(const unsigned int k)
{
register unsigned int l = 0, r = 12;
while (l < r)
{
if ((1ll << (l + r + 1 >> 1)) > k)
{
r = (l + r + 1 >> 1) - 1;
}
else
{
l = (l + r + 1 >> 1);
}
}
return l;
}
unsigned int tag[MAXN], maxn[MAXN];
// void pushdown(unsigned int id)
// {
// if (tag[id] == 0)
// {
// return;
// }
// tag[(id << 2) + 1] = maxn[(id << 2) + 1] = tag[id];
// tag[(id << 2) + 2] = maxn[(id << 2) + 2] = tag[id];
// tag[(id << 2) + 3] = maxn[(id << 2) + 3] = tag[id];
// tag[(id << 2) + 4] = maxn[(id << 2) + 4] = tag[id];
// tag[id] = 0;
// }
// void pushup(unsigned int id)
// {
// // cout << "pushup " << id << " " << maxn[(id << 2) + 1] << " " << maxn[(id << 2) + 2] << " " << maxn[(id << 2) + 3] << " " << maxn[(id << 2) + 4] << endl;
// maxn[id] = max(maxn[id], maxn[(id << 2) + 1]);
// maxn[id] = max(maxn[id], maxn[(id << 2) + 2]);
// maxn[id] = max(maxn[id], maxn[(id << 2) + 3]);
// maxn[id] = max(maxn[id], maxn[(id << 2) + 4]);
// }
// void buildtree(const unsigned int id, const unsigned int u, const unsigned int d, const unsigned int l, const unsigned int r)
// {
// // cout << id << ": u=" << u << " d=" << d << " l=" << l << " r=" << r << endl;
// // cout << id << " " << u << " " << d << " " << l << " " << r << endl;
// if (u == d && l == r)
// {
// return;
// }
// const unsigned int midx = (u + d) / 2, midy = (l + r) / 2;
// buildtree((id << 2) + 1, u, midx, l, midy);
// buildtree((id << 2) + 2, midx + 1, d, l, midy);
// buildtree((id << 2) + 3, u, midx, midy + 1, r);
// buildtree((id << 2) + 4, midx + 1, d, midy + 1, r);
// }
unsigned int query(const unsigned int id, const unsigned int u, const unsigned int d, const unsigned int l, const unsigned int r, const unsigned int x, const unsigned int y, const unsigned int z, const unsigned int w)
{
if (x > y || z > w || y < u || x > d || w < l || z > r)
{
return 0;
}
pushdown(id);
// cout << "query id=" << id << ": u=" << u << " d=" << d << " l=" << l << " r=" << r << " x=" << x << " y=" << y << " z=" << z << " w=" << w << endl;
if (x == u && y == d && z == l && w == r)
{
// cout << "Over " << maxn[id] << endl;
return maxn[id];
}
if (u == d && l == r)
{
return 0;
}
const unsigned int midx = (u + d) / 2, midy = (l + r) / 2;
register unsigned int ans = 0;
ans = max(ans, query((id << 2) + 1, u, midx, l, midy, x, min(y, midx), z, min(w, midy)));
ans = max(ans, query((id << 2) + 2, midx + 1, d, l, midy, max(midx + 1, x), y, z, min(w, midy)));
ans = max(ans, query((id << 2) + 3, u, midx, midy + 1, r, x, min(y, midx), max(midy + 1, z), w));
ans = max(ans, query((id << 2) + 4, midx + 1, d, midy + 1, r, max(midx + 1, x), y, max(midy + 1, z), w));
// cout << id << " " << maxn[1] << endl;
return ans;
}
void update(const unsigned int id, const unsigned int u, const unsigned int d, const unsigned int l, const unsigned int r, const unsigned int x, const unsigned int y, const unsigned int z, const unsigned int w, const unsigned int k)
{
if (x > y || z > w || y < u || x > d || w < l || z > r)
{
return;
}
// cout << "update id=" << id << ": u=" << u << " d=" << d << " l=" << l << " r=" << r << " x=" << x << " y=" << y << " z=" << z << " w=" << w << " k=" << k << endl;
pushdown(id);
if (x == u && y == d && z == l && w == r)
{
// cout << "Over\n";
tag[id] = maxn[id] = k;
return;
}
if (u == d && l == r)
{
return;
}
const unsigned int midx = (u + d) / 2, midy = (l + r) / 2;
update((id << 2) + 1, u, midx, l, midy, x, min(y, midx), z, min(w, midy), k);
update((id << 2) + 2, midx + 1, d, l, midy, max(midx + 1, x), y, z, min(w, midy), k);
update((id << 2) + 3, u, midx, midy + 1, r, x, min(y, midx), max(midy + 1, z), w, k);
update((id << 2) + 4, midx + 1, d, midy + 1, r, max(midx + 1, x), y, max(midy + 1, z), w, k);
pushup(id);
}
signed main()
{
register int n, m, t, d, s, w, x, y, U, D, L, R, nowmax;
read(n, m, t);
n = (1 << (log2_(n) + 1));
m = (1 << (log2_(m) + 1));
// buildtree(0, 1, n, 1, m);
while (t--)
{
read(d, s, w, x, y);
U = x + 1;
D = x + d;
L = y + 1;
R = y + s;
nowmax = query(0, 1, n, 1, m, U, D, L, R);
// for (unsigned int i = 0; i <= 84; i++)
// {
// cout << i << " " << maxn[i] << " " << tag[i] << endl;
// }
// cout << endl;
update(0, 1, n, 1, m, U, D, L, R, nowmax + w);
// cout << endl;
// for (unsigned int i = 0; i <= 84; i++)
// {
// cout << i << " " << maxn[i] << " " << tag[i] << endl;
// }
// cout << endl << endl;
}
write((int)maxn[0]);
return 0;
}
加载中...