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

一直RE,数据都能过,但是就是RE,哪位好心人帮忙看看吧..

Posted by salvete at 2018-08-23 19:28:20 on Problem 2528
/*************************************************************************
	> File Name: mian.cpp
	> Author:Eagles 
	> Mail:None 
	> Created Time: 2018年08月23日 星期四 14时11分57秒
	> Description:POJ2528 
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define N 200000
#define lc root<<1
#define rc root<<1|1
int n;
struct node
{
    int l,r,lz;
}tree[N*10];

int mess[N][2];

bool color[N];

void build(int root, int l, int r)
{
    tree[root].l=l;
    tree[root].r=r;
    tree[root].lz=-1;
    if (l == r)
    {
        return;
    }
    int mid=(l+r)/2;
    build(lc,l,mid);
    build(rc,mid+1,r);
}

void pushdown(int root)
{
    if (tree[root].lz != -1&&(tree[root].l!=tree[root].r))
    {
        tree[lc].lz=tree[root].lz;
        tree[rc].lz=tree[root].lz;
        tree[root].lz=-1;
    }
}

void update(int root, int L, int R, int val)
{
    if (tree[root].l==L&&tree[root].r==R)
    {
        tree[root].lz=val;
        return;
    }

    pushdown(root);

    int mid=(tree[root].l+tree[root].r)/2;

    if (L>mid)
        update(rc,L,R,val);
    else if (R<=mid)
        update(lc,L,R,val);
    else
    {
        update(lc,L,mid,val);
        update(rc,mid+1,R,val);
    }
}

void query(int root,int L, int R)
{
    if (tree[root].lz!=-1)
    {
        color[tree[root].lz]=true;
             return;
    }
    

    int mid=(tree[root].l+tree[root].r)/2;

    if (L>mid)
        query(rc,L,R);
    else if (R<=mid)
        query(lc,L,R);
    else
    {
        query(lc,L,mid);
        query(rc,mid+1,R);
    }
}

int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
    int t;
    while(~scanf("%d",&t))
    {
        while (t--)
        {
            scanf("%d",&n);
            
            int mx=0;

            for (int i=1; i<=n; i++)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                if (a>b)
                    swap(a,b);
                if (a==0||b==0)
                    continue;
                mx=max(max(a,b),mx);
                mess[i][0]=a;
                mess[i][1]=b;
            }
            
            build(1,1,mx);

            for (int i=1; i<=n; i++)
            {
                update(1,mess[i][0],mess[i][1],i);
            }


            memset(color,false,sizeof(color));

            query(1,1,mx);

            int ans=0;

            for (int i=1; i<=n; i++)
                if (color[i])
                    ans++;

            printf("%d\n",ans);
        }
    }
    return 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