oj.uz

Submission #994473

# Submission time Handle Problem Language Result Execution time Memory
994473 2024-06-07T16:57:59 Z Alfraganus Wall (IOI14_wall) C++17
0 / 100
 77 ms 8176 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define print(a) for(auto x : a) cout << x << ' '; cout << endl;

struct SegTree {

    int size = 1;
    vector<int> mins, maxs;

    SegTree (int n){
        while(size < n)
            size <<= 1;
        mins.resize(2 * size, -1);
        maxs.resize(2 * size, -1);
    }

    void add(int l,  int r, int v, int x, int lx, int rx, int lastmin = -1, int lastmax = -1){
        if(maxs[x] != -1){
            if(maxs[x] <= v){
                if(lastmax == -1)
                    lastmax = maxs[x];
                else
                    lastmax = min(lastmax, maxs[x]);
                maxs[x] = -1;
            }
        }
        if(mins[x] != -1){
            if(mins[x] >= v and (lastmax == -1 or lastmax == v))
                return;
            lastmin = max(lastmin, mins[x]);
            mins[x] = -1;
        }
        if(l <= lx and rx <= r){
            mins[x] = max(mins[x], v);
            if(maxs[x] == -1)
                maxs[x] = lastmin;
            else
                maxs[x] = min(maxs[x], lastmin);
            maxs[x] = max(maxs[x], mins[x]);
            return;
        }
        if(r <= lx or rx <= l){
            if(lastmin != -1){
                mins[x] = max(mins[x], lastmin);
                if(maxs[x] != -1)
                    maxs[x] = max(maxs[x], mins[x]);
            }
            if(lastmax != -1){
                if(maxs[x] == -1)
                    maxs[x] = lastmax;
                else
                    maxs[x] = min(maxs[x], lastmax);
                mins[x] = min(mins[x], maxs[x]);
            }
            return;
        }
        int mid = (lx + rx) >> 1;
        add(l, r, v, (x << 1) + 1, lx, mid, lastmin, lastmax);
        add(l, r, v, (x << 1) + 2, mid, rx, lastmin, lastmax);
    }

    void add(int l, int r, int v){
        add(l, r, v, 0, 0, size);
    }

    void remove(int l, int r, int v, int x, int lx, int rx, int lastmin = -1, int lastmax = -1){
        if(mins[x] != -1){
            if(mins[x] >= v){
                lastmin = max(lastmin, mins[x]);
                mins[x] = -1;
            }
        }
        if(maxs[x] != -1){
            if(max(lastmin, maxs[x]) <= v)
                return;
            if(lastmax == -1)
                lastmax = maxs[x];
            else
                lastmax = min(lastmax, maxs[x]);
            maxs[x] = -1;
        }
        if(l <= lx and rx <= r){
            if(maxs[x] == -1)
                maxs[x] = v;
            else
                maxs[x] = min(maxs[x], v);
            mins[x] = max(mins[x], lastmin);
            mins[x] = min(mins[x], maxs[x]);
            return;
        }
        if(rx <= l or r <= lx){
            if(lastmax != -1){
                if(maxs[x] == -1)
                    maxs[x] = lastmax;
                else
                    maxs[x] = min(maxs[x], lastmax);
                mins[x] = min(mins[x], maxs[x]);
            }
            if(lastmin != -1){
                mins[x] = max(mins[x], lastmin);
                if(maxs[x] != -1)
                    maxs[x] = max(maxs[x], mins[x]);
            }
            return;
        }
        int mid = (lx + rx) >> 1;
        remove(l, r, v, (x << 1) + 1, lx, mid, lastmin, lastmax);
        remove(l, r, v, (x << 1) + 2, mid, rx, lastmin, lastmax);
    }

    void remove(int l, int r, int v){
        remove(l, r, v, 0, 0, size);
    }

    int query(int ind, int x, int l, int r){
        if(l + 1 == r){
            if(mins[x] == -1)
                return 0;
            return mins[x];
        }
        int mid = (l + r) >> 1;
        int ans = -1;
        if(ind < mid)
            ans = query(ind, (x << 1) + 1, l, mid);
        else
            ans = query(ind, (x << 1) + 2, mid, r);
        int left = max(0, mins[x]), right = (maxs[x] == -1 ? 1e9 : maxs[x]);
        if(left <= ans and ans <= right)
            return ans;
        else if(ans < left)
            return left;
        return right;
    }

    int query(int x){
        return query(x, 0, 0, size);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegTree s(n);
    for(int i = 0; i < k; i ++){
        if(op[i] == 1)
            s.add(left[i], right[i] + 1, height[i]);
        else
            s.remove(left[i], right[i] + 1, height[i]);
        // for(int j = 0; j < 2 * s.size - 1; j ++)
        //     cout << i << ' ' << j << ' ' << s.mins[j] << ' ' << s.maxs[j] << endl;
    }
    for(int i = 0; i < n; i ++)
        finalHeight[i] = s.query(i);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 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 348 KB Output is correct
2 Incorrect 77 ms 8176 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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