URAL

http://www.nocow.cn/index.php/Translate:URAL/1097

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<set>
#include<map>
#include<list>
#include<queue>
#include<vector>
#define tree int o,int l,int r
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define lo o<<1
#define ro o<<1|1
#define ULL unsigned long long
#define LL long long
#define UI unsigned int
#define inf 0x7fffffff
#define eps 1e-7
#define N 10009
#define M 901
using namespace std;
int T,n,m,k,t,maxv,q;
int sum[N<<2];
int ql,qr;
struct Node
{
    int d,len,x,y;
    bool operator<(const Node a)const
    {
        return d>a.d;
    }
} node[M];

void update(tree)
{
    if(ql<=l&&qr>=r)
    {
        sum[o]=r-l+1;
    }
    else if(sum[o]==r-l+1)
        return ;
    else
    {
        int mid=(l+r)>>1;
        if(ql<=mid)
            update(lson);
        if(qr>mid)
            update(rson);
        sum[o]=sum[lo]+sum[ro];
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("ex.in","r",stdin);
#endif
    int ncase=0;

    scanf("%d%d",&n,&m);
    scanf("%d",&q);
    for(int i=0; i<q; ++i)
        scanf("%d%d%d%d",&node[i].d,&node[i].len,&node[i].x,&node[i].y);
    sort(node,node+q);
    int minv=255;
    for(int i=m; i<=n; i++)
    {
        memset(sum,0,sizeof(sum));
        ql=n-m+1,qr=n;
        update(1,1,n);
        int flag=1;
        for(int j=0; j<q; ++j)
        {
            if(i>=node[j].y&&i<=node[j].y+node[j].len-1+m-1)////WA
            {
                ql=node[j].x-m+1,qr=node[j].x+node[j].len-1;
                update(1,1,n);
            }
            if(sum[1]==n)
            {
                flag=0;
                minv=min(minv,node[j].d);
                break;
            }
        }
        if(flag)minv=1;
    }
    if(minv==255)
        puts("IMPOSSIBLE");
    else
        printf("%d
",minv);
    return 0;
}