oj.uz

Submission #67869

# Submission time Handle Problem Language Result Execution time Memory
67869 2018-08-15T11:32:56 Z yp155136 Wall (IOI14_wall) C++14
0 / 100
 342 ms 35800 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13436 KB Output is correct
2 Incorrect 17 ms 13672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13680 KB Output is correct
2 Correct 342 ms 23840 KB Output is correct
3 Runtime error 297 ms 35800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35800 KB Output is correct
2 Incorrect 19 ms 35800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 35800 KB Output is correct
2 Incorrect 16 ms 35800 KB Output isn't correct
3 Halted 0 ms 0 KB -