oj.uz

Submission #289176

# Submission time Handle Problem Language Result Execution time Memory
289176 2020-09-02T12:40:13 Z emil_physmath Wall (IOI14_wall) C++17
61 / 100
 1099 ms 41976 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 = 200'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 9 ms 12800 KB Output is correct
2 Correct 10 ms 12928 KB Output is correct
3 Correct 10 ms 12928 KB Output is correct
4 Correct 20 ms 13048 KB Output is correct
5 Correct 18 ms 13056 KB Output is correct
6 Correct 20 ms 13056 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12800 KB Output is correct
2 Correct 183 ms 20728 KB Output is correct
3 Correct 354 ms 16248 KB Output is correct
4 Correct 1041 ms 21288 KB Output is correct
5 Correct 521 ms 21880 KB Output is correct
6 Correct 509 ms 21880 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12800 KB Output is correct
2 Correct 12 ms 12928 KB Output is correct
3 Correct 11 ms 12928 KB Output is correct
4 Correct 20 ms 13056 KB Output is correct
5 Correct 17 ms 13184 KB Output is correct
6 Correct 17 ms 13056 KB Output is correct
7 Correct 8 ms 12800 KB Output is correct
8 Correct 181 ms 20728 KB Output is correct
9 Correct 336 ms 16248 KB Output is correct
10 Correct 987 ms 21368 KB Output is correct
11 Correct 518 ms 21752 KB Output is correct
12 Correct 498 ms 21784 KB Output is correct
13 Correct 8 ms 12800 KB Output is correct
14 Correct 186 ms 20728 KB Output is correct
15 Correct 67 ms 13560 KB Output is correct
16 Correct 1091 ms 21736 KB Output is correct
17 Correct 523 ms 21496 KB Output is correct
18 Correct 512 ms 21572 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12800 KB Output is correct
2 Correct 10 ms 12960 KB Output is correct
3 Correct 11 ms 12928 KB Output is correct
4 Correct 20 ms 13056 KB Output is correct
5 Correct 17 ms 13056 KB Output is correct
6 Correct 17 ms 13048 KB Output is correct
7 Correct 8 ms 12800 KB Output is correct
8 Correct 180 ms 20728 KB Output is correct
9 Correct 339 ms 16248 KB Output is correct
10 Correct 995 ms 21256 KB Output is correct
11 Correct 521 ms 21880 KB Output is correct
12 Correct 498 ms 21752 KB Output is correct
13 Correct 9 ms 12800 KB Output is correct
14 Correct 188 ms 20644 KB Output is correct
15 Correct 68 ms 13432 KB Output is correct
16 Correct 1099 ms 21624 KB Output is correct
17 Correct 518 ms 21624 KB Output is correct
18 Correct 505 ms 21624 KB Output is correct
19 Runtime error 234 ms 41976 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -