oj.uz

Submission #791753

# Submission time Handle Problem Language Result Execution time Memory
791753 2023-07-24T09:35:19 Z caganyanmaz Wall (IOI14_wall) C++14
100 / 100
 618 ms 52608 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 5 ms 840 KB Output is correct
5 Correct 4 ms 804 KB Output is correct
6 Correct 6 ms 840 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 268 ms 37652 KB Output is correct
3 Correct 189 ms 17352 KB Output is correct
4 Correct 563 ms 41764 KB Output is correct
5 Correct 412 ms 42368 KB Output is correct
6 Correct 420 ms 40744 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 704 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 828 KB Output is correct
5 Correct 4 ms 804 KB Output is correct
6 Correct 4 ms 804 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 257 ms 37584 KB Output is correct
9 Correct 239 ms 17372 KB Output is correct
10 Correct 528 ms 41756 KB Output is correct
11 Correct 449 ms 42372 KB Output is correct
12 Correct 406 ms 40708 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 266 ms 37644 KB Output is correct
15 Correct 26 ms 3100 KB Output is correct
16 Correct 581 ms 41740 KB Output is correct
17 Correct 404 ms 41168 KB Output is correct
18 Correct 415 ms 41236 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 700 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 5 ms 804 KB Output is correct
5 Correct 4 ms 804 KB Output is correct
6 Correct 4 ms 804 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 265 ms 37656 KB Output is correct
9 Correct 193 ms 17360 KB Output is correct
10 Correct 557 ms 41832 KB Output is correct
11 Correct 407 ms 42356 KB Output is correct
12 Correct 407 ms 40744 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 260 ms 37544 KB Output is correct
15 Correct 26 ms 3084 KB Output is correct
16 Correct 618 ms 41788 KB Output is correct
17 Correct 438 ms 41316 KB Output is correct
18 Correct 417 ms 41184 KB Output is correct
19 Correct 513 ms 52516 KB Output is correct
20 Correct 534 ms 50004 KB Output is correct
21 Correct 512 ms 52560 KB Output is correct
22 Correct 514 ms 50272 KB Output is correct
23 Correct 521 ms 50004 KB Output is correct
24 Correct 514 ms 50084 KB Output is correct
25 Correct 507 ms 50112 KB Output is correct
26 Correct 520 ms 52608 KB Output is correct
27 Correct 510 ms 52592 KB Output is correct
28 Correct 506 ms 50072 KB Output is correct
29 Correct 501 ms 50080 KB Output is correct
30 Correct 506 ms 50104 KB Output is correct