D. Monitor Educational Codeforces Round 28

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define E 2.7182818284
const ll mod=1e9+;//
const int maxn=5e2+; struct node
{
int x,y,t;
}f[maxn*maxn]; int K,s,t,a[maxn][maxn],tot[maxn][maxn]={}; int cmp(node a,node b)
{
return a.t<b.t;
} bool judge()
{
int i,j;
for (i=K;i<=s;i++)
for (j=K;j<=t;j++)
if (tot[i][j]-tot[i-K][j]-tot[i][j-K]+tot[i-K][j-K]==K*K)
return ;
return ;
} int main()
{
int q,i,j,l,r,m;
scanf("%d%d%d%d",&s,&t,&K,&q);
for (i=;i<=q;i++)
scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].t); sort(f+,f+q+,cmp); l=,r=q;
while (l<=r)
{
memset(a,,sizeof(a));
m=(l+r)>>; for (i=;i<=m;i++)
a[f[i].x][f[i].y]=;
for (i=;i<=s;i++)
for (j=;j<=t;j++)
tot[i][j]=tot[i-][j]+tot[i][j-]-tot[i-][j-]+a[i][j];
if (judge())
r=m-;
else
l=m+;
}
if (l==q+)
printf("-1");
else
printf("%d",f[l].t);
return ;
}
/*
2 2 2 4
1 2 1
1 1 4
2 2 3
2 1 2 2 2 1 4
1 2 1
1 1 4
2 2 3
2 1 2 2 2 2 0
*/