oj.uz

Submission #784006

# Submission time Handle Problem Language Result Execution time Memory
784006 2023-07-15T14:18:42 Z canadavid1 Wall (IOI14_wall) C++14
24 / 100
 367 ms 26140 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define clamp(x,l,r) x=min(r,max(x,l))
#define all(x) begin(x),end(x)

struct Node
{
    int ls=0;
    int when=-1;
    int le,re;
    Node *lc,*rc;
    Node() {}
    Node(int le, int re) : le(le), re(re) {}
    Node(int le, int re,Node* lc, Node* rc) : le(le), re(re), lc(lc),rc(rc) {}
    
    void set(int l, int r, int val,int time)
    {
        l = max(l,le);
        r = min(r,re);
        if(l>=r) return;
        if(l==le && r==re) {ls = val;when=time;return;}
        if(ls != -1)
        {
            if(lc) {lc->ls = ls;lc->when = when;}
            if(rc) {rc->ls = ls;lc->when = when;}
            ls = -1;
            when = -1;
        }
        if(lc) lc->set(l,r,val,time);
        if(rc) rc->set(l,r,val,time);

    }
    void propdown(vector<pair<int,int>>& out)
    {
        if(re - le <= 1) 
        {
            out[le].first = ls;
            out[le].second = when;
            return;
        }
        if(ls != -1)
        {
            if(lc) {lc->ls = ls;lc->when = when;}
            if(rc) {rc->ls = ls;lc->when = when;}
            ls = -1;
            when = -1;
        }
        if(lc) lc->propdown(out);
        if(rc) rc->propdown(out);

    }
    
    void prn(string before="")
    {
        cout << /* object info*/ ls << " " << le << " " << re << "\n";
        if(lc != nullptr || rc != nullptr)
        {
            cout << before << "+-";
            before.append("| ");
            if(lc == nullptr) cout << "nullptr\n";
            else lc->prn(before);
            before.pop_back();before.pop_back();
        }
        if(rc != nullptr)
        {
            cout << before << "'-";
            before.append("  ");
            if(rc == nullptr) cout << "nullptr\n";
            else rc->prn(before);
            before.pop_back();before.pop_back();
        }
    }
};


template<typename... args>
Node* newNode(args... a)
{
    static Node* arr = nullptr;
    static int count = 1024;
    if(count >= 1024)
    {
        arr = new Node[1024];
        count = 0;
    }
    arr[count].~Node();
    return new(&arr[count++]) Node(a...);
}

Node* makeTree(int l, int r)
{
    if (r-1 <= l) return newNode(l,r,nullptr,nullptr);
    int m = (r+l)/2; // could be other heuristic
    return newNode(l,r,makeTree(l,m),makeTree(m,r));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    // lazy update segment tree
    Node* a = makeTree(0,n);
    vector<tuple<int,int,int,int,int>> ops(k);
    for(int i = 0; i < k; i++) ops[i] = {op[i],height[i],left[i],right[i],i};
    sort(all(ops));
    for(int i = 0; i < k && get<0>(ops[i]) != 2; i++)
    {
        int p,h,l,r,time;
        tie(p,h,l,r,time) = ops[i];
        a->set(l,r+1,h,time);
    }
    vector<pair<int,int>> minima(n);
    a->propdown(minima);
    a->set(0,n,INT_MAX,-1);
    for(int i = k-1; i >= 0 && get<0>(ops[i]) != 1; --i)
    {
        int p,h,l,r,time;
        tie(p,h,l,r,time) = ops[i];
        a->set(l,r+1,h,time);
    }
    vector<pair<int,int>> maxima(n);
    a->propdown(maxima);
    for(int i = 0; i < n; i++)
    {
        // assuming minima happen before maxima
        finalHeight[i] = min(minima[i].first,maxima[i].first);
    }

    return;
}

Subtask #1
0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 156 ms 17940 KB Output is correct
3 Correct 131 ms 9080 KB Output is correct
4 Correct 367 ms 26140 KB Output is correct
5 Correct 219 ms 26124 KB Output is correct
6 Correct 224 ms 26140 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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