oj.uz

Submission #595269

# Submission time Handle Problem Language Result Execution time Memory
595269 2022-07-13T14:02:59 Z thezomb1e Wall (IOI14_wall) C++17
100 / 100
 1214 ms 59340 KB 
#include "wall.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)

using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;

//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;

//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> void mins(T& x, T y) {x = min(x, y);}
template<typename T> void maxs(T& x, T y) {x = max(x, y);}
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

//order_of_key(k): number of elements strictly less than k
//find_by_order(k): k-th element in the set

void setPrec() {cout << fixed << setprecision(15);}
void unsyncIO() {cin.tie(0)->sync_with_stdio(0);}
void setIn(string s) {freopen(s.c_str(), "r", stdin);}
void setOut(string s) {freopen(s.c_str(), "w", stdout);}
void setIO(string s = "") {
    unsyncIO(); setPrec();
    if(s.size()) setIn(s + ".in"), setOut(s + ".out");
}

// #define TEST_CASES

struct SegmentTree {

    struct Node {
        int mx, mn;
    };

    vector<Node> tre;
    const int NO_OPERATION = 0;
    const int NEUTRAL = IINF;
    int sz;

    SegmentTree(int n) {
        sz = 1;
        while (sz < n) sz *= 2;
        tre.assign(2 * sz, {0, IINF});
    }

    void propagate(int x, int lx, int rx) {
        if (rx - lx == 1) return;
        maxs(tre[2 * x].mx, tre[x].mx);
        maxs(tre[2 * x].mn, tre[x].mx);
        mins(tre[2 * x].mn, tre[x].mn);
        mins(tre[2 * x].mx, tre[x].mn);
        maxs(tre[2 * x + 1].mn, tre[x].mx);
        maxs(tre[2 * x + 1].mx, tre[x].mx);
        mins(tre[2 * x + 1].mn, tre[x].mn);
        mins(tre[2 * x + 1].mx, tre[x].mn);
        tre[x].mx = 0; tre[x].mn = IINF;
    }

    void set(int l, int r, int op, int v, int x, int lx, int rx) {
        propagate(x, lx, rx);
        if (rx <= l || lx >= r) {
            return;
        }
        if (l <= lx && r >= rx) {
            if (op == 1) {
                maxs(tre[x].mx, v);
                maxs(tre[x].mn, v);
            } else {
                mins(tre[x].mn, v);
                mins(tre[x].mx, v);
            }
            return;
        }
        int m = (lx + rx) / 2;
        set(l, r, op, v, 2 * x, lx, m);
        set(l, r, op, v, 2 * x + 1, m, rx);
    }

    void set(int l, int r, int op, int v) {
        set(l, r, op, v, 1, 0, sz);
    }

    int get(int i, int x, int lx, int rx) {
        propagate(x, lx, rx);
        if (rx - lx == 1) {
            return tre[x].mx;
        }
        int m = (lx + rx) / 2;
        if (i < m) {
            return get(i, 2 * x, lx, m);
        } else {
            return get(i, 2 * x + 1, m, rx);
        }
    }

    int get(int i) {
        return get(i, 1, 0, sz);
    }
};


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegmentTree st(n);
    for (int i = 0; i < k; i++) {
        st.set(left[i], right[i] + 1, op[i], height[i]);
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = st.get(i);
    }
}

Compilation message

wall.cpp: In function 'void setIn(std::string)':
wall.cpp:43:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 | void setIn(string s) {freopen(s.c_str(), "r", stdin);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
wall.cpp: In function 'void setOut(std::string)':
wall.cpp:44:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 | void setOut(string s) {freopen(s.c_str(), "w", stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 6 ms 756 KB Output is correct
6 Correct 6 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 122 ms 13912 KB Output is correct
3 Correct 187 ms 7824 KB Output is correct
4 Correct 591 ms 20184 KB Output is correct
5 Correct 356 ms 20724 KB Output is correct
6 Correct 363 ms 19148 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 2 ms 440 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 7 ms 724 KB Output is correct
5 Correct 7 ms 724 KB Output is correct
6 Correct 8 ms 716 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 120 ms 13820 KB Output is correct
9 Correct 221 ms 7924 KB Output is correct
10 Correct 537 ms 20300 KB Output is correct
11 Correct 364 ms 20668 KB Output is correct
12 Correct 342 ms 19100 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 132 ms 13880 KB Output is correct
15 Correct 32 ms 1896 KB Output is correct
16 Correct 527 ms 20176 KB Output is correct
17 Correct 359 ms 19496 KB Output is correct
18 Correct 364 ms 19600 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 724 KB Output is correct
5 Correct 9 ms 696 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 123 ms 13892 KB Output is correct
9 Correct 193 ms 8020 KB Output is correct
10 Correct 576 ms 20192 KB Output is correct
11 Correct 427 ms 20700 KB Output is correct
12 Correct 346 ms 19180 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 125 ms 13904 KB Output is correct
15 Correct 43 ms 1868 KB Output is correct
16 Correct 532 ms 20180 KB Output is correct
17 Correct 354 ms 19600 KB Output is correct
18 Correct 401 ms 19480 KB Output is correct
19 Correct 1214 ms 59208 KB Output is correct
20 Correct 1142 ms 59212 KB Output is correct
21 Correct 1138 ms 59176 KB Output is correct
22 Correct 1161 ms 59340 KB Output is correct
23 Correct 1174 ms 59208 KB Output is correct
24 Correct 1144 ms 59188 KB Output is correct
25 Correct 1184 ms 59300 KB Output is correct
26 Correct 1192 ms 59288 KB Output is correct
27 Correct 1191 ms 59128 KB Output is correct
28 Correct 1157 ms 59272 KB Output is correct
29 Correct 1173 ms 59260 KB Output is correct
30 Correct 1158 ms 59200 KB Output is correct