oj.uz

Submission #733549

# Submission time Handle Problem Language Result Execution time Memory
733549 2023-05-01T02:56:41 Z Julto Wall (IOI14_wall) C++14
0 / 100
 221 ms 8032 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

struct Node{
	int type, level;
} tree[8000105];

void pushdown(int v, int l, int r){
    int mid = (l + r) / 2;
    if(v * 2 + 2 < 8000105){
        if(tree[v].type == 1){
            if(tree[v * 2 + 1].level < tree[v].level || (tree[v * 2 + 1].type == 0)){
                tree[v * 2 + 1] = tree[v];
            }
            if(tree[v * 2 + 2].level < tree[v].level || (tree[v * 2 + 2].type == 0)){
                tree[v * 2 + 2] = tree[v];
            }
        }
        if(tree[v].type == 2){
            if(tree[v * 2 + 1].level > tree[v].level || (tree[v * 2 + 1].type == 0)){
                tree[v * 2 + 1] = tree[v];
            }
            if(tree[v * 2 + 2].level > tree[v].level || (tree[v * 2 + 2].type == 0)){
                tree[v * 2 + 2] = tree[v];
            }
            
        }
    }
    
    tree[v].type = 0;
}

void upd(int v, int l, int r, int lq, int rq, int t, int x){
    pushdown(v, l, r);
    if(l >= rq || lq >= r){
        return;
    }
    if(l >= lq && r <= rq){
        if(t == 1){
            if(tree[v].level < x || l != r - 1){
                tree[v].type = t, tree[v].level = x;
            }
        }
        else{
            if(tree[v].level > x || l != r - 1){
                tree[v].type = t, tree[v].level = x;
            }
        }
        pushdown(v, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(v * 2 + 1, l, mid, lq, rq, t, x);
    upd(v * 2 + 2, mid, r, lq, rq, t, x);

}

void taketree(int v, int l, int r, vector<int> &ans){
    pushdown(v, l, r);
    //cout << l << " " << r << " " << tree[v].type << " " << tree[v].level << '\n';
    if(l == r - 1){
        ans[l] = tree[v].level;
        return;
    }
    int mid = (l + r) / 2;
    
    taketree(v * 2 + 1, l, mid, ans);
    taketree(v * 2 + 2, mid, r, ans);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    upd(0, 0, n, 0, n, 1, 0);
    for(int i = 0; i < k; i++){
        upd(0, 0, n, left[i], right[i] + 1, op[i], height[i]);
    }
    vector<int> ans(n);
    taketree(0, 0, n, ans);
    for(int i = 0; i < n; i++){
        finalHeight[i] = ans[i];
        //cout << ans[i] << " ";
    }
}

Compilation message

wall.cpp: In function 'void pushdown(int, int, int)':
wall.cpp:10:9: warning: unused variable 'mid' [-Wunused-variable]
   10 |     int mid = (l + r) / 2;
      |         ^~~

Subtask #1
0 / 8.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 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 130 ms 8032 KB Output is correct
3 Incorrect 221 ms 4744 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.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 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
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 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -