Submission #289177

#	Time	Username	Problem	Language	Result	Execution time	Memory
289177		emil_physmath	Wall (IOI14_wall)	C++17	100 / 100	1756 ms	152056 KiB

wall

#include "wall.h"
#include <algorithm>
#include <iostream>
#include <random>
#include <chrono>
using namespace std;
using llong = long long;
#define BUGO(x) cerr << #x << " = " << (x) << '\n';
#define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';}
#ifndef MANSON
#define BUGO(x)
#define BUGOARR(x)
#endif
ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
	out << "{" << p.first << ", " << p.second << "}";
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
const int maxN = 2'000'000;
struct Upd {
    pair<int, char> a, b;
    Upd()
        : a(0, 'U')
        , b(1000'000'000, 'D')
    {}
};
Upd operator+(Upd l, pair<int, char> i) {
    if (l.b.second == i.second) {
        if (i.second == 'U' && i.first > l.b.first) l.b = i;
        if (i.second == 'D' && i.first < l.b.first) l.b = i;
        return l;
    }
    if (l.b.second == 'U') {
        if (i.first <= l.b.first || (l.a.first > l.b.first && i.first < l.a.first)) {
            l.a = l.b;
            l.b = i;
        }
    }
    else if (i.first >= l.b.first || (l.a.first < l.b.first && i.first > l.a.first)) {
        l.a = l.b;
        l.b = i;
    }
    return l;
}
Upd operator+(Upd l, const Upd& r) { return l + r.a + r.b; }

Upd lazy[4 * maxN];

inline void Push(int v)
{
    if (v * 2 + 1 < 4 * maxN) {
        lazy[v * 2] = lazy[v * 2] + lazy[v];
        lazy[v * 2 + 1] = lazy[v * 2 + 1] + lazy[v];
    }
    lazy[v] = Upd();
}
void Update(int v, int vl, int vr, int l, int r, const pair<int, char>& upd)
{
    if (l > vr || vl > r) return;
    if (l <= vl && vr <= r) {
        lazy[v] = lazy[v] + upd;
        return;
    }
    Push(v);
    int vm = (vl + vr) / 2;
    Update(v * 2, vl, vm, l, r, upd);
    Update(v * 2 + 1, vm + 1, vr, l, r, upd);
}
Upd Get(int v, int vl, int vr, int i)
{
    if (vl == vr)
        return lazy[v];
    int vm = (vl + vr) / 2;
    if (i <= vm)
        return Get(v * 2, vl, vm, i) + lazy[v];
    return Get(v * 2 + 1, vm + 1, vr, i) + lazy[v];
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[])
{
    for (int i = 0; i < k; ++i)
        Update(1, 0, n - 1, left[i], right[i], make_pair(height[i], op[i] == 1 ? 'U' : 'D'));
    for (int i = 0; i < n; ++i)
    {
        Upd upd = Get(1, 0, n - 1, i);
        ans[i] = 0;
        for (const pair<int, char>& x: {upd.a, upd.b})
            if (x.second == 'U')
                ans[i] = max(ans[i], x.first);
            else
                ans[i] = min(ans[i], x.first);
    }
}

Compilation message (stderr)

wall.cpp:11: warning: "BUGO" redefined
   11 | #define BUGO(x)
      | 
wall.cpp:8: note: this is the location of the previous definition
    8 | #define BUGO(x) cerr << #x << " = " << (x) << '\n';
      | 
wall.cpp:12: warning: "BUGOARR" redefined
   12 | #define BUGOARR(x)
      | 
wall.cpp:9: note: this is the location of the previous definition
    9 | #define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';}
      | 
wall.cpp:14:46: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   14 | ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
      |                                              ^~~~
wall.cpp:14:52: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   14 | ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
      |                                                    ^~~~
wall.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::pair<_T1, _T2>&)':
wall.cpp:16:1: warning: no return statement in function returning non-void [-Wreturn-type]
   16 | }
      | ^

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