Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎报名第四届北京大学游戏对抗邀请赛!

虐狗!

Posted by 770605294 at 2016-08-18 14:11:26 on Problem 2482
#include <stdio.h>
#include <algorithm>
#define prince scanf
#define princess printf
#define add(x) node[x].add
#define sum(x) node[x].sum
#define ls(x) node[x].l
#define rs(x) node[x].r
#define wisdom struct
#define fleeting_time __int64
#define beauti void
#define glamorous return
#define gay int
#define love_story if
#define girlfriend for
#define boyfriend while
#define singledog else
#define cheek bool
#define cute true
#define pretty false
#define I_just_love_one_person using namespace
I_just_love_one_person std;
wisdom line
{
    fleeting_time x,y1,y2,val;
}love[10010*2];
wisdom tree
{
    gay l,r;         
    fleeting_time sum,add;       
}node[10010*8];
fleeting_time y[10010*2];
cheek cmp (line a,line b) 
{
    love_story (a.x < b.x)
        glamorous cute;
    love_story (a.x == b.x&&a.val > b.val)
        glamorous cute;
    glamorous pretty;
}
beauti Build (fleeting_time left,fleeting_time right,int u)
{
    node[u].l = left;
    node[u].r = right;
    node[u].sum = node[u].add = 0;
    love_story (left == right)
        glamorous ;
    gay mid = (left + right)>>1;
    Build (left,mid,u<<1);
    Build (mid+1,right,u<<1|1);
}
fleeting_time maxium(fleeting_time a,fleeting_time b)
{
    glamorous a > b ? a : b;
}
beauti getdown (gay i)
{
    sum(i<<1)+=add(i);
    add(i<<1)+=add(i);
    sum(i<<1|1)+=add(i);
    add(i<<1|1)+=add(i);
    add(i)= 0;
}
beauti pushup(gay i)
{
	sum(i)=maxium(sum(i<<1),sum(i<<1|1));
}
beauti update (fleeting_time left,fleeting_time right,fleeting_time val,int u)     
{                                                                   
    love_story (left == y[node[u].l] && y[node[u].r] == right)
    {
        node[u].sum += val;
        node[u].add += val;
        glamorous;
    }
    love_story (node[u].l == node[u].r)
        glamorous;
    love_story (node[u].add)
        getdown (u);
    gay mid = (node[u].l + node[u].r)>>1;
    love_story (right <= y[mid])
        update (left,right,val,u<<1);
    singledog love_story (left >= y[mid+1])
        update (left,right,val,u<<1|1);
    singledog
    {
        update (left,y[mid],val,u<<1);
        update (y[mid+1],right,val,u<<1|1);
    }
    pushup(u);
}                                                         
gay main ()
{
    gay n,w,h;
    boyfriend (~prince("%d%d%d",&n,&w,&h))
    {
        girlfriend (gay i = 0;i < n;i ++)
        {
            prince("%I64d %I64d %I64d",&love[i].x,&love[i].y1,&love[i].val);
            y[i*2+1] = love[i].y1;                              
            y[i*2+2] = love[i].y1 + h - 1;
            love[i].y2 = love[i].y1 + h - 1;
            love[n+i]  = love[i] ;
            love[n+i].x = love[i].x + w - 1;
            love[n+i].val = -love[i].val;            
        }
        sort (y+1,y + 2*n + 1);
        sort (love,love + 2*n,cmp);
        gay cnt = unique (y + 1, y + 2*n + 1) - y -1;
        Build (1,cnt,1);
        fleeting_time ans = 0;
        girlfriend (gay i = 0;i < 2*n;i ++)
        {
            update(love[i].y1,love[i].y2,love[i].val,1);
            ans = max (ans,node[1].sum);
        }
        princess("%I64d\n",ans);
    }
    glamorous 0;
}



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator