oj.uz

Submission #974386

# Submission time Handle Problem Language Result Execution time Memory
974386 2024-05-03T09:32:04 Z hariaakas646 Wall (IOI14_wall) C++14
24 / 100
 1977 ms 73308 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

template <class T>
struct SegTree
{
    int size = 1, n;
    vector<T> segtree;
    vector<T> vec;

    T def; // Assign a value

    void init(int l, T defv)
    {
        n = l;
        def = defv;

        while (size < n)
            size *= 2;

        segtree.assign(2 * size, def);
        vec.assign(size, def);
    }

    T operation(T x, T y)
    {
        T out;
        if(x.f > y.f && x.f <= y.s) {
          out.f = x.f;
        }
        else {
          out.f = y.f;
        }
        if(x.s < y.s && x.s >= y.f) {
          out.s = x.s;
        }
        else {
          out.s = y.s;
        } 
        return out;
    }

    void recalculate(int x)
    {
        segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]);
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            segtree[x] = vec[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * x + 1, l, mid);
        build(2 * x + 2, mid + 1, r);
        recalculate(x);
    }

    void build()
    {
        build(0, 0, size - 1);
    }

    void set(int id, T val)
    {
        vec[id] = val;
    }

    void update(int x, int l, int r, int id, T val)
    {
        if (l == r)
        {
            segtree[x] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (id <= mid)
        {
            update(2 * x + 1, l, mid, id, val);
        }
        else
        {
            update(2 * x + 2, mid + 1, r, id, val);
        }
        recalculate(x);
    }

    void update(int id, T val)
    {
        update(0, 0, size - 1, id, val);
    }

    T query(int x, int l, int r, int lx, int rx)
    {
        if (lx > r || rx < l)
        {
            return def;
        }
        if (lx <= l && r <= rx)
        {
            return segtree[x];
        }
        int mid = (l + r) / 2;
        T v1 = query(2 * x + 1, l, mid, lx, rx);
        T v2 = query(2 * x + 2, mid + 1, r, lx, rx);
        return operation(v1, v2);
    }

    T query(int lx, int rx)
    {
        return query(0, 0, size - 1, lx, rx);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  set<pii> st;
  frange(i, k) {
    st.insert(mp(left[i], i));
  }
  SegTree<pii> seg;
  seg.init(k, mp(-1, 1e9));
  seg.build();
  
  seti add, rem;
  set<pii> act;
  frange(i, n) {
    while(st.size() && (*st.begin()).f == i) {
      int id = (*st.begin()).s;
      st.erase(st.begin());
      if(op[id] == 1) {
        add.insert(id);
        seg.update(id, mp(height[id], 1e9));
      }
      else {
        rem.insert(id);
        seg.update(id, mp(-1, height[id]));
      }
      act.insert(mp(right[id]+1, id));
    }
    while(act.size() && (*act.begin()).f == i) {
      int id = (*act.begin()).s;
      act.erase(act.begin());
      if(op[id] == 1) {
        add.erase(id);
        seg.update(id, mp(-1, 1e9));
      }
      else {
        rem.erase(id);
        seg.update(id, mp(-1, 1e9));
      }
    }
    int ai=-1, ri=-1;
    if(add.size()) ai = *prev(add.end());
    if(rem.size()) ri = *prev(rem.end());
    if(ai == -1) {
      finalHeight[i] = 0;
    }
    else if(ai > ri) {
      finalHeight[i] = seg.query(0, k-1).f;
    }
    else {
      finalHeight[i] = seg.query(0, k-1).s;
    }
  }
  return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 4 ms 1116 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 348 KB Output is correct
2 Correct 439 ms 73308 KB Output is correct
3 Correct 584 ms 25812 KB Output is correct
4 Correct 1977 ms 62364 KB Output is correct
5 Correct 619 ms 56088 KB Output is correct
6 Correct 557 ms 54440 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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