/ Randle /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Wrong Answer 成绩取消 0ms 0 Bytes

代码

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int tree[65536][4],n,m,c,i,MIN,ans;
struct node
{
    int x;
    int y;
    int z;
};
node A[100005];
int cmp(node i,node j)
{
    return i.y<j.y;
}
void Update(int k)
{
    tree[k*2][2]+=tree[k][3];
    tree[k*2+1][2]+=tree[k][3];
    tree[k*2][3]+=tree[k][3];
    tree[k*2+1][3]+=tree[k][3];
    tree[k][3]=0;
}
void work(int root,int l,int r,int k)
{
    if (l==tree[root][0] && r==tree[root][1])
    {
        tree[root][2]+=k;
        tree[root][3]+=k;
        return;
    }
    Update(root);
    int mid=(tree[root][0]+tree[root][1])/2;
    if (l<=mid) work(root*2,l,min(mid,r),k);
    if (r>mid) work(root*2+1,max(mid+1,l),r,k);
    tree[root][2]=min(tree[root*2][2],tree[root*2+1][2]);
}
int find(int root,int l,int r)
{
    if (l==tree[root][0] && r==tree[root][1]) return tree[root][2];
    Update(root);
    int mid=(tree[root][0]+tree[root][1])/2,p=453266144,q=453266144;
    if (l<=mid) p=find(root*2,l,min(mid,r));
    if (r>mid) q=find(root*2+1,max(mid+1,l),r);
    return min(p,q);
}
int main()
{
    scanf("%d%d%d",&n,&m,&c);
    for (i=32768; i<=65535; i++) tree[i][0]=tree[i][1]=i;
    for (i=32767; i>=1; i--)
    {
        tree[i][0]=tree[i*2][0];
        tree[i][1]=tree[i*2+1][1];
    }
    work(1,1+32767,m+32767,c);
    for (i=1; i<=n; i++)
    {
        scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].z);
        A[i].y--;
    }
    sort(A+1,A+n+1,cmp);
    for (i=1; i<=n; i++)
    {
        MIN=find(1,A[i].x+32767,A[i].y+32767);
        if (MIN>A[i].z)
        {
            work(1,A[i].x+32767,A[i].y+32767,-A[i].z);
            ans+=A[i].z;
        }
        else
        {
            work(1,A[i].x+32767,A[i].y+32767,-MIN);
            ans+=MIN;
        }
    }
    cout<<ans;
    return 0;
}

信息

递交者
类型
递交
题目
公交与怪兽 T2
题目数据
下载
语言
C++
递交时间
2017-10-03 13:54:53
评测时间
2017-11-02 15:34:56
评测机
分数
0
总耗时
0ms
峰值内存
0 Bytes