Submission #50479

#	Time	Username	Problem	Language	Result	Execution time	Memory
50479		antimirage	Wall (IOI14_wall)	C++17	0 / 100	3069 ms	242352 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 5;

struct st
{
    int t, v, o;

    st(){
        t = v = o = -1;
    }

    st(int a, int b, int c)
    {
        t = a;
        v = b;
        o = c;
    }
};
vector <st> t[N * 4], vec;

int n;

void update (int time, int type, int l, int r, int val, int v = 1, int tl = 1, int tr = n)
{
    if (l > tr || tl > r)
        return;

    if (l <= tl && tr <= r)
    {
        t[v].emplace_back( st( time, val, type ) );
        return;
    }
    int tm = (tl + tr) >> 1;
    update (time, type, l, r, val, v + v, tl, tm);
    update (time, type, l, r, val, v + v + 1, tm + 1, tr);
}
void Do (int pos, int v = 1, int tl = 1, int tr = n)
{
    if (pos > tr || pos < tl) return;

    for (auto to : t[v])
        vec.emplace_back(to);

    if(tl == tr) return;

    int tm = (tl + tr) >> 1;
    Do( pos, v + v, tl, tm );
    Do( pos, v + v + 1, tm + 1, tr );
}
bool cmp (st a, st b)
{
    return a.t < b.t;
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int ans[])
{
    n = N;
    for (int i = 0; i < k; i++)
        update( i, op[i], left[i] + 1, right[i] + 1, height[i] );

    for (int i = 1; i <= n; i++)
    {
        vec.clear();
        Do( i );
        sort( vec.begin(), vec.end() , cmp);

//        cout<<i << endl;
//
//        for (auto to : vec)
//        {
//            cout << to.t << " " << to.v << " " << to.o << endl;
//        }
//        system("pause");

        st a, b;

        int fl = -1;

        for (auto to : vec)
        {
            if (fl != -1)
            {
                if (to.o == 1 && to.v > fl)
                    fl = to.v;
                else if (to.o == 2 && to.v < fl)
                    fl = to.v;
                continue;
            }

            if (a.t == -1)
                a = to;
            else if (b.t == -1)
            {
                if (to.o == 1)
                {
                    if (a.o == 2)
                    {
                        if (a.v <= to.v)
                            fl = to.v;
                        else
                            b = to;
                    }
                    else if (to.v > a.v)
                        a = to;
                }
                else
                {
                    if (a.o == 1)
                    {
                        if (a.v >= to.v)
                            fl = to.v;
                        else
                            b = to;
                    }
                    else if (to.v < a.v)
                        a = to;
                }
            }
            else
            {
                if (to.o == 1 && to.v > a.v)
                    a = to;
                else if (to.o == 2 && to.v < b.v)
                    b = to;
            }
            if (a.o == 2 && b.o == 1)
                swap(a, b);
        }
        if (fl != -1)
            ans[i - 1] = fl;
        else
        {
            if (a.o == 2)
                ans[i - 1] = 0;
            else
                ans[i - 1] = (a.v == -1 ? 0 : a.v);
        }
    }
}

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