oj.uz

Submission #289177

# Submission time Handle Problem Language Result Execution time Memory
289177 2020-09-02T12:41:25 Z emil_physmath Wall (IOI14_wall) C++17
100 / 100
 1756 ms 152056 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 75 ms 125560 KB Output is correct
2 Correct 77 ms 125688 KB Output is correct
3 Correct 78 ms 125560 KB Output is correct
4 Correct 91 ms 125688 KB Output is correct
5 Correct 88 ms 125688 KB Output is correct
6 Correct 89 ms 125688 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 125560 KB Output is correct
2 Correct 258 ms 133496 KB Output is correct
3 Correct 412 ms 129016 KB Output is correct
4 Correct 1066 ms 134136 KB Output is correct
5 Correct 596 ms 134648 KB Output is correct
6 Correct 570 ms 134520 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 125560 KB Output is correct
2 Correct 80 ms 125688 KB Output is correct
3 Correct 82 ms 125564 KB Output is correct
4 Correct 92 ms 125688 KB Output is correct
5 Correct 89 ms 125688 KB Output is correct
6 Correct 88 ms 125688 KB Output is correct
7 Correct 78 ms 125560 KB Output is correct
8 Correct 259 ms 133624 KB Output is correct
9 Correct 411 ms 128888 KB Output is correct
10 Correct 1082 ms 134036 KB Output is correct
11 Correct 592 ms 134520 KB Output is correct
12 Correct 577 ms 134628 KB Output is correct
13 Correct 79 ms 125560 KB Output is correct
14 Correct 267 ms 133404 KB Output is correct
15 Correct 138 ms 126328 KB Output is correct
16 Correct 1165 ms 134228 KB Output is correct
17 Correct 597 ms 134392 KB Output is correct
18 Correct 585 ms 134264 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 125560 KB Output is correct
2 Correct 82 ms 125688 KB Output is correct
3 Correct 81 ms 125560 KB Output is correct
4 Correct 98 ms 125688 KB Output is correct
5 Correct 92 ms 125688 KB Output is correct
6 Correct 89 ms 125688 KB Output is correct
7 Correct 79 ms 125504 KB Output is correct
8 Correct 261 ms 133496 KB Output is correct
9 Correct 414 ms 129144 KB Output is correct
10 Correct 1075 ms 134136 KB Output is correct
11 Correct 591 ms 134520 KB Output is correct
12 Correct 575 ms 134648 KB Output is correct
13 Correct 79 ms 125560 KB Output is correct
14 Correct 265 ms 133500 KB Output is correct
15 Correct 138 ms 126200 KB Output is correct
16 Correct 1193 ms 134520 KB Output is correct
17 Correct 593 ms 134268 KB Output is correct
18 Correct 580 ms 134264 KB Output is correct
19 Correct 1708 ms 151492 KB Output is correct
20 Correct 1703 ms 149464 KB Output is correct
21 Correct 1704 ms 151928 KB Output is correct
22 Correct 1694 ms 149524 KB Output is correct
23 Correct 1701 ms 149456 KB Output is correct
24 Correct 1695 ms 149496 KB Output is correct
25 Correct 1709 ms 149496 KB Output is correct
26 Correct 1709 ms 151928 KB Output is correct
27 Correct 1756 ms 152056 KB Output is correct
28 Correct 1701 ms 149880 KB Output is correct
29 Correct 1710 ms 149496 KB Output is correct
30 Correct 1724 ms 149496 KB Output is correct