Submission #67869

#	Time	Username	Problem	Language	Result	Execution time	Memory
67869		yp155136	Wall (IOI14_wall)	C++14	0 / 100	342 ms	35800 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000007;
const int P = 21*20000;

struct Node
{
    static Node mem[P];
    Node *lc,*rc;
    int mx,mn;
    bool have;
    Node():lc(NULL),rc(NULL),mn(0),mx(-INF),have(0){}
} Node::mem[P],*ptr = Node::mem;

Node* Build(int L,int R)
{
    Node* node = new(ptr++)Node();
    if (L == R) return node;
    int mid=(L+R)>>1;
    node->lc = Build(L,mid);
    node->rc = Build(mid+1,R);
    return node;
}

void push(Node* node,int L,int R)
{
    if (L == R) return;
    if (!node->have) return;
    node->lc->have = node->rc->have = true;
    if (node->mx == -INF)
    {
        if (node->lc->mx == -INF)
        {
            node->lc->mn = max(node->lc->mn,node->mn);
        }
        else
        {
            node->lc->mx = -INF;
            node->lc->mn = node->mn;
        }
        if (node->rc->mx == -INF)
        {
            node->rc->mn = max(node->rc->mn,node->mn);
        }
        else
        {
            node->rc->mx = -INF;
            node->rc->mn = node->mn;
        }
    }
    else
    {
        if (node->lc->mn == INF)
        {
            node->lc->mx = min(node->lc->mx,node->mx);
        }
        else
        {
            node->lc->mn = -INF;
            node->lc->mx = node->mx;
        }
        if (node->rc->mn == INF)
        {
            node->rc->mx = min(node->rc->mx,node->mx);
        }
        else
        {
            node->rc->mn = -INF;
            node->rc->mx = node->mx;
        }
    }
    node->have = false;
    return;
}

void modify(Node* node,int L,int R,int l,int r,int type,int val)
{
    if (l>R || L>r) return;
    else if (l <= L && R <= r)
    {
        node->have = true;
        if (type == 1)
        {
            //set minimum;
            if (node->mn == INF)
            {
                if (node->mx > val)
                {
                    ;
                }
                else
                {
                    node->mx = INF;
                    node->mn = val;
                }
            }
            else
            {
                node->mn = max(node->mn,val);
            }
        }
        else if (type == 2)
        {
            //set maximum
            if (node->mx == -INF)
            {
                if (node->mn < val)
                {
                    ;
                }
                else
                {
                    node->mn = INF;
                    node->mx = val;
                }
            }
            else
            {
                node->mx = min(node->mx,val);
            }
        }
        return;
    }
    push(node,L,R);
    int mid=(L+R)>>1;
    modify(node->lc,L,mid,l,r,type,val);
    modify(node->rc,mid+1,R,l,r,type,val);
    return;
}

const int N = 2000006;

int ans[N];

void visit(Node* node,int L,int R)
{
    if (L == R)
    {
        if (node->mn == INF) ans[L] = node->mx;
        else ans[L] = node->mn;
        return;
    }
    push(node,L,R);
    int mid=(L+R)>>1;
    visit(node->lc,L,mid);
    visit(node->rc,mid+1,R);
}

void buildWall(int n, int m, int op[], int L[], int R[], int h[], int H[])
{
    ptr = Node::mem;
    Node* root = Build(0,n-1);
    vector<int> v;
    for (int i=0;m>i;i++)
    {
        v.push_back(h[i]);
    }
    v.push_back(0);
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end()) - v.begin());
    for (int i=0;m>i;i++)
    {
        modify(root,0,n-1,L[i],R[i],op[i],lower_bound(v.begin(),v.end(),h[i]) - v.begin());
    }
    visit(root,0,n-1);
    for (int i=0;n>i;i++) H[i] = v[ans[i]];
}

Compilation message (stderr)

wall.cpp: In constructor 'Node::Node()':
wall.cpp:12:12: warning: 'Node::mn' will be initialized after [-Wreorder]
     int mx,mn;
            ^~
wall.cpp:12:9: warning:   'int Node::mx' [-Wreorder]
     int mx,mn;
         ^~
wall.cpp:14:5: warning:   when initialized here [-Wreorder]
     Node():lc(NULL),rc(NULL),mn(0),mx(-INF),have(0){}
     ^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39