Submission #1206052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206052		goulthen	Wall (IOI14_wall)	C++20	61 / 100	394 ms	13972 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#define pii pair<int,int>
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define fi first
#define se second

const int MAXN = 1e5;
const int INF = 1e9;

struct Node {
int v;
};
 
struct Seg3 {
    Node seg3[4*MAXN];
    pii lazy[4*MAXN];

    void apply(int i, int tp, int x) {
        if (tp == 1) {
          lazy[i].fi = max(lazy[i].fi, x);
          lazy[i].se = max(lazy[i].se, lazy[i].fi);
        } else if (tp == 2) {
          lazy[i].se = min(lazy[i].se, x);
          lazy[i].fi = min(lazy[i].fi, lazy[i].se);
        }
        seg3[i].v = max(lazy[i].fi, seg3[i].v);
        seg3[i].v = min(lazy[i].se, seg3[i].v);
    }

    void flush(int i, int l, int r) {
      //cout << i<< ' ' << l<< ' ' << r << ' ' << lazy[i].fi << ' ' << lazy[i].se << '\n';
        seg3[i].v = max(lazy[i].fi, seg3[i].v);
        seg3[i].v = min(lazy[i].se, seg3[i].v);
        if (l==r) return;
        apply(2*i, 1,lazy[i].fi);
        apply(2*i, 2,lazy[i].se);

        apply(2*i+1, 1,lazy[i].fi);
        apply(2*i+1, 2,lazy[i].se);
        lazy[i] = {0, INF}; 
    }
    Node join(Node a, Node b) {
        Node r;
        r.v = a.v;
        return r;
    }
 
    void build(int i, int l, int r) {
        lazy[i] = {0,INF};
        if (l == r) {
            seg3[i] = {0};
            return;
        }
        int mid =(l+r)>>1;
        build(2*i,l,mid);
        build(2*i+1,mid+1,r);
        seg3[i] = join(seg3[2*i],seg3[2*i+1]);
    }
 
    Seg3(int n) {
        build(1,1,n);
    }
    void update1(int i, int l, int r, int tl, int tr, int x) {
        flush(i,l,r);
        if (tr < l || tl > r) return;
        if (l>=tl && r <= tr) {
            apply(i,1,x);
            return;
        }
        int mid =(l+r)>>1;
        update1(2*i,l,mid,tl,tr,x);
        update1(2*i+1,mid+1,r,tl,tr,x);
        seg3[i] = join(seg3[2*i],seg3[2*i+1]);
    }
    void update2(int i, int l, int r, int tl, int tr, int x) {
        flush(i,l,r);
        if (tr < l || tl > r) return;
        if (l>=tl && r <= tr) {
            apply(i,2,x);
            return;
        }
        int mid =(l+r)>>1;
        update2(2*i,l,mid,tl,tr,x);
        update2(2*i+1,mid+1,r,tl,tr,x);
        seg3[i] = join(seg3[2*i],seg3[2*i+1]);
    }
    int query(int i, int l, int r, int tl, int tr) {
        flush(i,l,r);
        if (tr < l || tl > r) return 0;
        if (l >= tl && r <= tr) return seg3[i].v;
        int mid = (l+r)>>1;
        return query(2*i,l,mid,tl,tr) + query(2*i+1,mid+1,r,tl,tr);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  Seg3 seg3(n);
  rep(i,0,k-1) {
    if (op[i] == 1) seg3.update1(1,1,n,left[i]+1,right[i]+1,height[i]);
    else seg3.update2(1,1,n,left[i]+1,right[i]+1,height[i]);
  }

  rep(i,0,n-1) finalHeight[i] = seg3.query(1,1,n,i+1,i+1);
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39