Submission #791753

#	Time	Username	Problem	Language	Result	Execution time	Memory
791753		caganyanmaz	Wall (IOI14_wall)	C++14	100 / 100	618 ms	52608 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define pb push_back
#define mp(x...) array<int,2>({x})
using namespace std;

//#define DEBUGGING

#ifdef DEBUGGING
#define debug(x) cout << (#x) << ": " << x << "\n"
#else
#define debug(x)
#endif


int k;
constexpr static int MXSIZE = 5e5;
constexpr static int MXST = MXSIZE<<2;
constexpr static int MXHEIGHT = 1e5;
constexpr static int MNHEIGHT = 0;

array<int, 2> st[MXST];

array<int, 2> merge(array<int, 2> l, array<int, 2> r)
{
        return mp(min(max(l[0], r[0]), r[1]), max(min(l[1], r[1]), r[0]));
}

void create()
{
        for (int i = 1; i < (k<<2); i++) st[i] = mp(MNHEIGHT, MXHEIGHT);
}

void update(int l, int r, int index, int i, array<int, 2> val)
{
        if (i >= r || l > i)
                return;
        if (l + 1 == r)
        {
                st[index] = val;
                return;
        }
        int m = l+r>>1;
        update(l, m, index<<1, i, val);
        update(m, r, (index<<1)|1, i, val);
        st[index] = merge(st[index<<1], st[(index<<1)|1]);
}

array<int, 2> query(int l, int r, int index, int ss, int ee)
{
        if (l >= ee || ss >= r)
                return mp(MNHEIGHT, MXHEIGHT);
        if (ee >= r && l >= ss)
                return st[index];
        int m = l+r>>1;
        array<int, 2> lres = query(l, m, index<<1, ss, ee);
        array<int, 2> rres = query(m, r, (index<<1)|1, ss, ee);
        return merge(lres, rres);
}

void update(int i, array<int, 2> val) { update(0, k, 1, i, val); }
array<int, 2> query(int ss, int ee) { return query(0, k, 1, ss, ee); }



void buildWall(int n, int kk, int op[], int left[], int right[], int height[], int finalHeight[])
{
        k = kk;
        create();
        vector<array<int, 2>> lq, rq;
        for (int i = 0; i < k; i++)
        {
                lq.pb(mp(left[i], i));
                rq.pb(mp(right[i]+1, i));
        }
        sort(lq.begin(), lq.end());
        sort(rq.begin(), rq.end());
        int lj = 0, rj = 0;
        for (int i = 0; i < n; i++)
        {
                while (lj < k && lq[lj][0] == i)
                {
                        int index = lq[lj][1];
                        if (op[index] == 1)
                                update(index, mp(height[index], MXHEIGHT));
                        else
                                update(index, mp(MNHEIGHT, height[index]));
                        lj++;
                }
                while (rj < k && rq[rj][0] == i) update(rq[rj++][1], mp(MNHEIGHT, MXHEIGHT));
                array<int, 2> res = query(0, k);
                finalHeight[i] = res[0];
        }
}

Compilation message (stderr)

wall.cpp: In function 'void update(int, int, int, int, std::array<int, 2>)':
wall.cpp:43:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int m = l+r>>1;
      |                 ~^~
wall.cpp: In function 'std::array<int, 2> query(int, int, int, int, int)':
wall.cpp:55:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int m = l+r>>1;
      |                 ~^~

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