oj.uz

Submission #289175

# Submission time Handle Problem Language Result Execution time Memory
289175 2020-09-02T12:39:22 Z emil_physmath Wall (IOI14_wall) C++17
61 / 100
 1319 ms 29308 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 = 100'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 5 ms 6528 KB Output is correct
2 Correct 8 ms 6656 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 24 ms 6784 KB Output is correct
5 Correct 14 ms 6812 KB Output is correct
6 Correct 14 ms 6784 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 190 ms 14584 KB Output is correct
3 Correct 401 ms 10216 KB Output is correct
4 Correct 1107 ms 15180 KB Output is correct
5 Correct 553 ms 15708 KB Output is correct
6 Correct 524 ms 15736 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 6 ms 6656 KB Output is correct
3 Correct 8 ms 6656 KB Output is correct
4 Correct 22 ms 6784 KB Output is correct
5 Correct 19 ms 6784 KB Output is correct
6 Correct 19 ms 6784 KB Output is correct
7 Correct 5 ms 6528 KB Output is correct
8 Correct 185 ms 14588 KB Output is correct
9 Correct 354 ms 10232 KB Output is correct
10 Correct 1008 ms 15224 KB Output is correct
11 Correct 525 ms 15736 KB Output is correct
12 Correct 543 ms 15864 KB Output is correct
13 Correct 5 ms 6528 KB Output is correct
14 Correct 197 ms 14648 KB Output is correct
15 Correct 63 ms 7288 KB Output is correct
16 Correct 1319 ms 15556 KB Output is correct
17 Correct 504 ms 15480 KB Output is correct
18 Correct 499 ms 15480 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 6 ms 6656 KB Output is correct
3 Correct 7 ms 6656 KB Output is correct
4 Correct 16 ms 6784 KB Output is correct
5 Correct 13 ms 6784 KB Output is correct
6 Correct 13 ms 6784 KB Output is correct
7 Correct 5 ms 6528 KB Output is correct
8 Correct 181 ms 14544 KB Output is correct
9 Correct 338 ms 10232 KB Output is correct
10 Correct 992 ms 15228 KB Output is correct
11 Correct 514 ms 15736 KB Output is correct
12 Correct 500 ms 15792 KB Output is correct
13 Correct 5 ms 6528 KB Output is correct
14 Correct 186 ms 14552 KB Output is correct
15 Correct 62 ms 7288 KB Output is correct
16 Correct 1091 ms 15480 KB Output is correct
17 Correct 505 ms 15608 KB Output is correct
18 Correct 503 ms 15496 KB Output is correct
19 Runtime error 223 ms 29308 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -