Submission #895960

#	Time	Username	Problem	Language	Result	Execution time	Memory
895960		SalihSahin	Wall (IOI14_wall)	C++14	100 / 100	698 ms	115540 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
#define pb push_back
#define mp make_pair
using namespace std;
 
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
 
struct SEGT{
    vector<int> mx, mn, lazy;
 
    void init(int n){
        lazy.assign(4*n, -1);
        mx.assign(4*n, 0);
        mn.assign(4*n, 0);
    }
 
    void push(int ind){
        if(lazy[ind] == -1) return;
        mx[ind*2] = lazy[ind];
        mx[ind*2+1] = lazy[ind];
        mn[ind*2] = lazy[ind];
        mn[ind*2+1] = lazy[ind];
        lazy[ind*2] = lazy[ind];
        lazy[ind*2+1] = lazy[ind];
 
        lazy[ind] = -1;
    }
 
    void update1(int ind, int l, int r, int ql, int qr, int val){
        if(l > r || l > qr || r < ql) return;
        if(l >= ql && r <= qr && mx[ind] <= val){
            lazy[ind] = val;
            mx[ind] = val;
            mn[ind] = val;
        }
        else if(l >= ql && r <= qr && mn[ind] >= val) return;
        else if(l == r){
            mx[ind] = max(mx[ind], val);
            mn[ind] = mx[ind];
        }
        else{
            push(ind);
            int m = (l + r)/2;
 
            update1(ind*2, l, m, ql, qr, val);
            update1(ind*2+1, m+1, r, ql, qr, val);
 
            mx[ind] = max(mx[ind*2], mx[ind*2+1]);
            mn[ind] = min(mn[ind*2], mn[ind*2+1]);
        }
    }
 
    void update2(int ind, int l, int r, int ql, int qr, int val){
        if(l > r || l > qr || r < ql) return;
        if(l >= ql && r <= qr && mn[ind] >= val){
            lazy[ind] = val;
            mx[ind] = val;
            mn[ind] = val;
        }
        else if(l >= ql && r <= qr && mx[ind] <= val) return;
        else if(l == r){
            mx[ind] = max(mx[ind], val);
            mn[ind] = mx[ind];
        }
        else{
            push(ind);
            int m = (l + r)/2;
 
            update2(ind*2, l, m, ql, qr, val);
            update2(ind*2+1, m+1, r, ql, qr, val);
 
            mx[ind] = max(mx[ind*2], mx[ind*2+1]);
            mn[ind] = min(mn[ind*2], mn[ind*2+1]);
        }
    }
 
    int query(int ind, int l, int r, int pos){
        if(l == r) return mx[ind];
        else{
            push(ind);
            int m = (l + r)/2;
 
            if(pos <= m) return query(ind*2, l, m, pos);
            else return query(ind*2+1, m+1, r, pos);
        }
    }
 
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   SEGT seg;
   seg.init(n);
   for(int i = 0; i < k; i++){
     if(op[i] == 1) seg.update1(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
     else seg.update2(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
   }
 
   for(int i = 0; i < n; i++){
     finalHeight[i] = seg.query(1, 1, n, i+1);
   }
}

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