oj.uz

Submission #529940

# Submission time Handle Problem Language Result Execution time Memory
529940 2022-02-24T05:52:42 Z Evang Wall (IOI14_wall) C++17
100 / 100
 666 ms 69580 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb(x) push_back(x)
#define eb(args...) emplace_back(args)
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


static const int N = 8e6+5;
static int n, n2, q;
struct node {
    int min, max;
//    int min = 0, max = inf;  // min is the minimum value needed to be
};
static vc<node> tr;

static void push(int i){
    if(i >= n)
        return;

    if(tr[i].min){
        tr[2*i].min = max(tr[2*i].min, tr[i].min);
        tr[2*i].max = max(tr[2*i].max, tr[i].min);

        tr[2*i+1].min = max(tr[2*i+1].min, tr[i].min);
        tr[2*i+1].max = max(tr[2*i+1].max, tr[i].min);
        tr[i].min = 0;
    }
    if(tr[i].max!=inf){
        tr[2*i].max = min(tr[2*i].max, tr[i].max);
        tr[2*i].min = min(tr[2*i].min, tr[i].max);
        tr[2*i+1].max = min(tr[2*i+1].max, tr[i].max);
        tr[2*i+1].min = min(tr[2*i+1].min, tr[i].max);

        tr[i].max = inf;
    }
}

static void upd_min(int l, int r, int i, int il, int ir, int x){
    if(ir < l || r < il)
        return;
    if(l <= il && ir <= r){
        tr[i].min = max(tr[i].min, x);
        tr[i].max = max(tr[i].max, x);
        return;
    }

    push(i);
    int im = (il+ir)/2;
    upd_min(l, r, 2*i, il, im, x);
    upd_min(l, r, 2*i+1, im+1, ir, x);
}

static void upd_max(int l, int r, int i, int il, int ir, int x){
    if(ir < l || r < il)
        return;
    if(l <= il && ir <= r){
        tr[i].max = min(tr[i].max, x);
        tr[i].min = min(tr[i].min, x);
        return;
    }

    push(i);
    int im = (il+ir)/2;
    upd_max(l, r, 2*i, il, im, x);
    upd_max(l, r, 2*i+1, im+1, ir, x);
}

static int at(int i){
    i += n;
    int ans = 0;
    while(i>0){
        ans = max(ans, tr[i].min);
        ans = min(ans, tr[i].max);
        i /= 2;
    }
    return ans;
}

void buildWall(int _n, int q, int op[], int left[], int right[], int height[], int finalHeight[]){
    n2 = _n;
    n = 1;
    while(n<n2)
        n *= 2;
    tr = vc<node>(2*n+5);
    for(auto&[x, y]: tr) {
        x = 0;
        y = inf;
    }

    for(int i = 0; i < q; ++i){
//        int t, l, r, h;
//        cin >> t >> l >> r >> h;
        int t = op[i], l = left[i], r = right[i], h = height[i];
        if(t==1)
            upd_min(l, r, 1, 0, n-1, h);
        else
            upd_max(l, r, 1, 0, n-1, h);
    }

    for(int i = 0; i < n2; ++i)
        finalHeight[i] = at(i);
}


//signed main() {
//    ios::sync_with_stdio(0); cin.tie(0);
//    cout << fixed; clog << fixed; clog << unitbuf;
//#ifdef _DEBUG
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    freopen("debug.txt", "w", stderr);
//#else
//    //freopen(".in", "r", stdin);
//    //freopen(".out", "w", stdout);
//#endif
//
//    cin >> n2 >> q;
//    for(int i = 0; i < n2; ++i)
//        cout << at(i) << sp;
//}

Compilation message

wall.cpp:63:19: warning: 'q' defined but not used [-Wunused-variable]
   63 | static int n, n2, q;
      |                   ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 126 ms 13880 KB Output is correct
3 Correct 138 ms 7908 KB Output is correct
4 Correct 351 ms 20320 KB Output is correct
5 Correct 270 ms 21384 KB Output is correct
6 Correct 213 ms 19816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 808 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 128 ms 13892 KB Output is correct
9 Correct 132 ms 7948 KB Output is correct
10 Correct 349 ms 20436 KB Output is correct
11 Correct 241 ms 21424 KB Output is correct
12 Correct 229 ms 19856 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 129 ms 13944 KB Output is correct
15 Correct 24 ms 1988 KB Output is correct
16 Correct 420 ms 20612 KB Output is correct
17 Correct 218 ms 20000 KB Output is correct
18 Correct 227 ms 19968 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 5 ms 684 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 125 ms 13868 KB Output is correct
9 Correct 137 ms 8024 KB Output is correct
10 Correct 351 ms 20392 KB Output is correct
11 Correct 227 ms 21444 KB Output is correct
12 Correct 232 ms 19904 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 135 ms 13896 KB Output is correct
15 Correct 32 ms 1988 KB Output is correct
16 Correct 406 ms 20688 KB Output is correct
17 Correct 229 ms 20052 KB Output is correct
18 Correct 225 ms 20012 KB Output is correct
19 Correct 577 ms 69552 KB Output is correct
20 Correct 599 ms 66928 KB Output is correct
21 Correct 570 ms 69540 KB Output is correct
22 Correct 599 ms 66924 KB Output is correct
23 Correct 609 ms 66928 KB Output is correct
24 Correct 581 ms 67088 KB Output is correct
25 Correct 666 ms 66988 KB Output is correct
26 Correct 597 ms 69580 KB Output is correct
27 Correct 598 ms 69452 KB Output is correct
28 Correct 571 ms 67184 KB Output is correct
29 Correct 595 ms 67036 KB Output is correct
30 Correct 640 ms 66952 KB Output is correct