https://contest.yandex.com/ioi/contest/567/problems/E/
首先，答案的正方形的長度可以二分搜，所以，我們可以先把問題轉成：有沒有一個長度為X的正方形，可以成功地放進格子裡面。
那，我們也可以輕易地算出：題目的那P個矩形中，每一個矩形會影響到多少 " 左上角放在某個格子的正方形 " ，注意到現在正方形的長度已經被限制成X了。
那，有了這些之後，我們就可以使用掃描線囉~
你需要一顆線段樹，可以支援：
(1) 區間加值
(2) 區間減值
(3) 查詢整體的min。
如果掃到某一個時間，當下整體的min <= B，那就代表可以放。
這樣的複雜度是O(P * log P * log( min(n,m) ))，最後一筆subtask過不了QAQ。
最後一筆有一個很神奇(?)的特性：B = 0。
首先，我們先定義一個一個函數 F(x1,x2)：代表說，在 x 座標是介於 [x1, x2]的區域中，連續 y 座標都是空的最大長度是多少。
可以發現： F(x1,x2) >= F(x1-1, x2) && F(x1,x2) >= F(x1,x2+1)
可以發現，如果固定x1，當x2越大的時候，F(x1,x2)會越來越小
當x2固定時，隨著x1越來越大，F(x1,x2)會越來越大
於是，我們可以使用雙指針來維護x1,x2，如果當下F(x1,x2) >= x2-x1+1，代表我們找到一個邊長為x2-x1+1的三角形，並且可以移動x2的指針。
如果當下F(x1,x2) < x2 - x1 +1，我們就要移動x1的指針的。
所以，我們需要一個資料結構(線段樹)，維護：
(1) 加入一個線段
(2) 刪除一個線段
(3) 查詢當前狀態的F值
可以用類似 " 區間連續最大和 " 的線段樹來解決。
//really hard QAQ
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pt;
typedef pair<int,int> pii;
typedef pair<pii,pii> Rec;
#define F first
#define S second
#define MP make_pair
#define SZ(x) ((int)(x).size())
int n,m,b;
int p;
const int N = 400006;
Rec rr[N];
Rec rrr[N];
int c[N];
vector<pii> Event[800006]; //MP(+ or - , index(to get y range) )
struct Node
{
static Node mem[4*200006];
Node *lc,*rc;
int mn,tag;
Node():lc(NULL),rc(NULL),tag(0),mn(0){}
void pull()
{
mn = min(lc->mn,rc->mn);
}
} Node::mem[4*200006],*ptr = Node::mem;
Node* Build(int L,int R)
{
Node* node = new(ptr++)Node();
if (L==R) return node;
int mid=(L+R)>>1;
node->lc = Build(L,mid);
node->rc = Build(mid+1,R);
return node;
}
void push(Node* node,int L,int R)
{
if (L==R) node->tag = 0;
if (node->tag == 0)return;
node->lc->mn += node->tag;
node->rc->mn += node->tag;
node->lc->tag += node->tag;
node->rc->tag += node->tag;
node->tag = 0;
return;
}
void modify(Node* node, int L,int R,int l,int r,int del)
{
if (l>R || L>r) return;
else if (l<=L &&R<=r)
{
node->mn += del;
node->tag += del;
return;
}
push(node,L,R);
int mid=(L+R)>>1;
modify(node->lc,L,mid,l,r,del);
modify(node->rc,mid+1,R,l,r,del);
node->pull();
return;
}
bitset<1000006> vis_x,vis_y,ee;
bool can_0(int len)
{
if (len >= min(n,m)+1) return false;
ptr = Node::mem;
int nn = n-len+1, mm = m-len+1;
int pp=0;
vector<int> vx,vy;
vis_x = ee;
vis_y = ee;
for (int i=1;p>=i;i++)
{
int x1 = rr[i].F.F - len+1;
int y1 = rr[i].F.S - len+1;
int x2 = rr[i].S.F;
int y2 = rr[i].S.S;
x1 = max(x1,1);
y1 = max(y1,1);
if (x1 <= nn && y1 <= mm)
{
x2 = min(x2,nn);
y2 = min(y2,mm);
//if (x1 == 1 && y1 == 1 && x2 == nn && y2 == mm) return false;
rrr[++pp] = MP( MP(x1,y1) , MP(x2,y2) );
if (!vis_x[x1]) vx.push_back(x1);
vis_x[x1] = true;
if (x2 + 1 <= nn && !vis_x[x2+1]) vx.push_back(x2+1);
vis_x[x2+1] = true;
if (!vis_y[y1]) vy.push_back(y1);
vis_y[y1] = true;
if (1 <= y1-1 && !vis_y[y1-1]) vy.push_back(y1-1);
vis_y[y1-1] = true;
if (!vis_y[y2]) vy.push_back(y2);
vis_y[y2] = true;
if (y2+1 <= mm && !vis_y[y2+1]) vy.push_back(y2+1);
vis_y[y2+1] = true;
}
}
if (pp == 0) return true;
vx.push_back(1); vx.push_back(nn);
vy.push_back(1); vy.push_back(mm);
sort(vx.begin(),vx.end()); vx.resize(unique(vx.begin(),vx.end()) - vx.begin());
sort(vy.begin(),vy.end()); vy.resize(unique(vy.begin(),vy.end()) - vy.begin());
//y axis --> segment tree
for (int i=0;SZ(vx)>=i;i++)
{
Event[i].clear();
}
for (int i=1;pp>=i;i++)
{
int x1=rrr[i].F.F;
int pos = lower_bound(vx.begin(),vx.end(),x1) - vx.begin() + 1;
Event[pos].push_back(make_pair(1,i));
rrr[i].F.S = lower_bound(vy.begin(),vy.end(),rrr[i].F.S) - vy.begin() + 1;
rrr[i].S.S = lower_bound(vy.begin(),vy.end(),rrr[i].S.S) - vy.begin() + 1;
}
//cout << "len = " << len << endl;
int mmm = SZ(vy);
Node* root = Build(1,mmm);
for (int i=1;SZ(vx)>=i;i++)
{
for (pii p:Event[i])
{
if (p.F == -1) modify(root,1,mmm,rrr[ p.S ].F.S,rrr[ p.S ].S.S,-c[ p.S ]);
else
{
modify(root,1,mmm,rrr[ p.S ].F.S,rrr[p.S].S.S, c[p.S] );
int x2 = rrr[p.S].S.F;
if (x2+1 <= nn)
{
int _ = x2+1;
int pos = lower_bound(vx.begin(),vx.end(),_) - vx.begin() + 1;
Event[pos].push_back(make_pair(-1,p.S));
}
}
}
push(root,1,mmm);
//cout << "i = " << i << " , len = " << len << " root->mn = " << root->mn << endl;
if (root->mn <= b)
{
return true;
}
}
return false;
//return true;
}
void solve()
{
for (int i=1;p>=i;i++)
{
scanf("%d %d %d %d %d",&rr[i].F.F,&rr[i].F.S,&rr[i].S.F,&rr[i].S.S,&c[i]);
}
int L=0,R=1000006;
while (R-L != 1)
{
int mid=(L+R)>>1;
//cout << "mid = " << mid << endl;
if (can_0(mid)) L = mid;
else R = mid;
}
printf("%d\n",L);
}
struct Sagiri
{
Sagiri *lc,*rc;
int Lmax,Rmax,midmax;
int cnt;
int L,R;
Sagiri(){}
Sagiri(int _L,int _R):L(_L),R(_R),Lmax(0),Rmax(0),midmax(0),cnt(0){}
void pull()
{
if (cnt)
{
Lmax = Rmax = midmax = 0;
return;
}
else if (L==R)
{
Lmax = Rmax = midmax = 1;
return;
}
int mid=(L+R)>>1;
Lmax = (lc->Lmax == mid-L+1 ? lc->Lmax + rc->Lmax : lc->Lmax);
Rmax = (rc->Rmax == R-mid ? rc->Rmax + lc->Rmax : rc->Rmax);
midmax = max( max( lc->midmax , rc->midmax ) , lc->Rmax + rc->Lmax );
}
};
Sagiri* Buildd(int L,int R)
{
Sagiri* sagiri = new Sagiri(L,R);
if (L==R)
{
sagiri->pull();
return sagiri;
}
int mid=(L+R)>>1;
sagiri->lc = Buildd(L,mid);
sagiri->rc = Buildd(mid+1,R);
sagiri->pull();
return sagiri;
}
void modifyy(Sagiri* sagiri,int L,int R,int l,int r,int del)
{
if (l>R || L>r) return;
else if (l<=L && R<=r)
{
sagiri->cnt += del;
sagiri->pull();
return;
}
int mid=(L+R)>>1;
modifyy(sagiri->lc,L,mid,l,r,del);
modifyy(sagiri->rc,mid+1,R,l,r,del);
sagiri->pull();
return;
}
const int P = 1000006;
vector<int> addd[P],subb[P];
int main ()
{
scanf("%d %d %d",&n,&m,&b);
scanf("%d",&p);
if (p <= 30000)
{
solve();
return 0;
}
Sagiri* root = Buildd(1,m);
for (int i=1;p>=i;i++)
{
scanf("%d %d %d %d %d",&rr[i].F.F,&rr[i].F.S,&rr[i].S.F,&rr[i].S.S,&c[i]);
addd[ rr[i].F.F ].push_back(i);
subb[ rr[i].S.F ].push_back(i);
}
int ans=0;
int L=1;
for (int R=1;n>=R;R++)
{
for (int i:addd[R])
{
modifyy(root,1,m,rr[i].F.S,rr[i].S.S,1);
}
//cout << "L = " << L << " , R = " << R<<" , midmax = " << root->midmax << endl;
if (root->midmax >= R-L+1) ans = max(ans,R-L+1);
while (root->midmax < R-L+1)
{
for (int i:subb[L])
{
modifyy(root,1,m,rr[i].F.S,rr[i].S.S,-1);
}
++L;
}
}
printf("%d\n",ans);
}
