oj.uz

Submission #762719

# Submission time Handle Problem Language Result Execution time Memory
762719 2023-06-21T16:52:13 Z rominanafu Wall (IOI14_wall) C++11
0 / 100
 343 ms 23212 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

struct ura {
    int val;
    vector<pii > lazy;
};

int n;
int alturas[100005];
ura ST[400005];

void agregar(int nodo, pii a) {
    if (a.first == 3) {
        while (!ST[nodo].lazy.empty())
            ST[nodo].lazy.pop_back();
    }
    if (ST[nodo].lazy.empty()) {
        ST[nodo].lazy.push_back(a);
        return;
    }
    pii b;
    for(int i=ST[nodo].lazy.size()-1; i>=0; i++) {
        b = ST[nodo].lazy[i];
        if (a.first == 1) {
            if (b.first == 3) {
                ST[nodo].lazy.push_back(a);
                break;
            } else if (b.first == 1) {
                ST[nodo].lazy[i].second = max(a.second, b.second);
                break;
            } else {
                if (b.second <= a.second) {
                    while (!ST[nodo].lazy.empty())
                        ST[nodo].lazy.pop_back();
                    ST[nodo].lazy.push_back({3, a.second});
                    break;
                }
                if (i-1 >= 0) {
                    if (ST[nodo].lazy[i-1].first == 1) {
                        b = ST[nodo].lazy[i-1];
                        ST[nodo].lazy[i-1] = ST[nodo].lazy[i];
                        ST[nodo].lazy[i] = {1, max(a.second, b.second)};
                        break;
                    }
                }
                ST[nodo].lazy.push_back(a);
            }
        } else {
            if (b.first == 3) {
                ST[nodo].lazy.push_back(a);
                break;
            } else if (b.first == 2) {
                ST[nodo].lazy[i].second = min(a.second, b.second);
                break;
            } else {
                if (b.second >= a.second) {
                    while (!ST[nodo].lazy.empty())
                        ST[nodo].lazy.pop_back();
                    ST[nodo].lazy.push_back({3, a.second});
                    break;
                }
                if (i-1 >= 0) {
                    if (ST[nodo].lazy[i-1].first == 2) {
                        b = ST[nodo].lazy[i-1];
                        ST[nodo].lazy[i-1] = ST[nodo].lazy[i];
                        ST[nodo].lazy[i] = {2, min(a.second, b.second)};
                        break;
                    }
                }
                ST[nodo].lazy.push_back(a);
            }
        }
    }
}

void propagar(int nodo,int ini, int fin) {
    while(!ST[nodo].lazy.empty()) {
        pii la = ST[nodo].lazy.back();
        if (la.first == 1)
            ST[nodo].val = max(ST[nodo].val, la.second);
        else if (la.first == 2)
            ST[nodo].val = min(ST[nodo].val, la.second);
        else
            ST[nodo].val = la.second;
        if (ini < fin) {
            agregar(nodo*2, la);
            agregar(nodo*2+1, la);
        }
        ST[nodo].lazy.pop_back();
    }
}

void actualizar(int &a, int &b, int &h, int &inst, int nodo=1, int ini=0, int fin=n-1) {
    propagar(nodo, ini, fin);
    if (a > fin || b < ini) {
        return;
    }
    if (a <= ini && fin <= b) {
        agregar(nodo, {inst, h});
        return;
    }
    int mid = (ini + fin) / 2;
    actualizar(a, b, h, inst, nodo*2, ini, mid);
    actualizar(a, b, h, inst, nodo*2+1, mid+1, fin);
    propagar(nodo*2, ini, mid);
    propagar(nodo*2+1, mid+1, fin);
}

void propagar_todo(int nodo=1, int ini=0, int fin=n-1) {
    propagar(nodo, ini, fin);
    if (ini == fin) {
        alturas[ini] = ST[nodo].val;
        return;
    }
    int mid = (ini + fin) / 2;
    propagar_todo(nodo*2, ini, mid);
    propagar_todo(nodo*2+1, mid+1, fin);
}

void buildWall(int N, int K, int op[], int l[], int r[], int H[], int finalHeight[]) {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
    int k, inst, a, b, h;
//    cin >> n >> k;
    n = N, k = K;
    for(int i=0; i<k; i++) {
        //cin >> inst >> a >> b >> h;
        inst = op[i], a=l[i], b=r[i], h=H[i];
        actualizar(a, b, h, inst);
        /// en inst:
        /// 1 es para agregar, es decir, max(alt[i], h)
        /// 2 es para quitar, es decir, min(alt[i], h)
    }
    propagar_todo();
    for(int i=0; i<n; i++) {
//        cout << alturas[i] << '\n';
        finalHeight[i] = alturas[i];
    }
//    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 8 ms 12972 KB Output is correct
3 Incorrect 9 ms 12884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12832 KB Output is correct
2 Correct 112 ms 23212 KB Output is correct
3 Incorrect 343 ms 19860 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12824 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Incorrect 9 ms 12880 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 7 ms 12972 KB Output is correct
3 Incorrect 9 ms 12844 KB Output isn't correct
4 Halted 0 ms 0 KB -