oj.uz

Submission #1113276

# Submission time Handle Problem Language Result Execution time Memory
1113276 2024-11-16T09:40:21 Z kiethm07 Wall (IOI14_wall) C++11
24 / 100
 593 ms 21716 KB 
#include <bits/stdc++.h>
#include <wall.h>

#define pii pair<int,int>
#define pli pair<long long,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
const ll linf = 1e16;
const double pi = acos(-1);

class IT{
private:
    vector<int> low, high;
public:
    IT (int n){
        low.resize(4 * n,0);
        high.resize(4 * n,inf);
    }
    void apply(int id,int x,int y){
        low[id] = max(low[id], x);
        high[id] = min(high[id], y);
        low[id] = min(low[id], high[id]);
        high[id] = max(high[id], low[id]);
    }
    void down(int id,int l,int r){
        if (l == r) return;
        apply(id * 2,low[id],high[id]);
        apply(id * 2 + 1,low[id],high[id]);
        low[id] = 0;
        high[id] = inf;
    }
    void update(int id,int l,int r,int u,int v,int f,int g){
        down(id,l,r);
        if (l > v || r < u) return;
        if (l >= u && r <= v){
            apply(id,f,g);
            down(id,l,r);
            return;
        }
        int mid = (l + r) / 2;
        update(id * 2,l,mid,u,v,f,g);
        update(id * 2 + 1,mid + 1,r,u,v,f,g);
//            cout << l << " " << r << " " << u << " " << v << " " << low[id] << " " << high[id] << "\n";

    }
    int query(int id,int l,int r,int i){
        down(id,l,r);
//        cout << l << " " << r << " " << low[id] << " " << high[id] << "\n";
        if (l > i || r < i) return -1;
        if (l == r){
            return low[id];
        }
        int mid = (l + r) / 2;
        int q1 = query(id * 2,l,mid,i);
        int q2 = query(id * 2 + 1,mid + 1,r,i);
        if (q1 == -1) return q2;
        return q1;
    }
};

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    IT t(n);
    for (int i = 0; i < k; i++){
        int l = left[i] + 1;
        int r = right[i] + 1;
//        cout << l << " " << r << " " << op[i] << " " << height[i] << "\n";
        if (op[i] == 1) t.update(1,1,n,l,r,height[i],inf);
        if (op[i] == 2) t.update(1,1,n,l,r,0,height[i]);
    }
    for (int i = 1; i <= n; i++){
        finalHeight[i - 1] = t.query(1,1,n,i);
//        cout << finalHeight[i - 1] << " ";
    }
}
//
//int main(){
//    #define TEXT "a"
//    cin.tie(0) -> sync_with_stdio(0);
//    if (fopen(TEXT".inp","r")){
//        freopen(TEXT".inp","r",stdin);
//        freopen(TEXT".out","w",stdout);
//    }
//    int n = 10, k = 6;
//    int op[k] = {1,2,2,1,1,2};
//    int left[k] = {1,4,3,0,2,6};
//    int right[k] = {8,9,6,5,2,7};
//    int height[k] = {4,1,5,3,5,0};
//    int finalHeight[n] = {};
//    buildWall(n,k,op,left,right,height,finalHeight);
//    return 0;
//}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 2 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 89 ms 13848 KB Output is correct
3 Correct 192 ms 8008 KB Output is correct
4 Correct 593 ms 21164 KB Output is correct
5 Correct 349 ms 21716 KB Output is correct
6 Correct 323 ms 20296 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 2 ms 452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 2 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -