Submission #1165683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165683		ty_mxzhn	Wall (IOI14_wall)	C++20	100 / 100	860 ms	89040 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
#define sz(x) (int)x.begin()
const int N = 2e6 + 7;
const int inf = 1e9 + 7;
pair < int , int > tree[4*N+7];
void init(){
    for(int i = 0;i<4*N+7;i++){
        tree[i] = {0,inf};
    }
}
pair < int , int > merge(pair < int , int > &a , pair < int , int > &b){
    pair < int , int > c;
    c.first = max(a.first , b.first);
    c.second = min(a.second , b.second);
    // cout << "noluo : " << c.first << " " << c.second << endl;
    if(c.first > c.second and a.first < b.first)
        c = {a.second , a.second};
    else if(c.first > c.second)
        c = {a.first , a.first};
    return c;
}
void push(int ind , int l , int r){
    if(tree[ind] != make_pair(0,inf)){
        if(l != r){
            tree[ind*2] = merge(tree[ind] , tree[ind*2]);
            tree[ind*2+1] = merge(tree[ind] , tree[ind*2+1]);
            tree[ind] = {0,inf};
        }
    }
}
void update(int ql , int qr , pair < int , int > ran , int ind=1 , int l=0 , int r=N){
    push(ind,l,r);
    if(l >= ql and r <= qr){
        // cout << "wtf : " << tree[ind].first << "," << tree[ind].second << " / " << ran.first << " " << ran.second << endl;
        auto tf = merge(ran , tree[ind]);
        // cout << "tf : " << tf.first << " " << tf.second << endl;
        tree[ind] = tf;
        // cout << "added " << l << " " << r << " " << tree[ind].first << " " << tree[ind].second << endl;
        push(ind,l,r);
        return;
    }
    else if(l > qr or r < ql)return;
    int mid = (l + r) / 2;
    update(ql,qr,ran,ind*2,l,mid);
    update(ql,qr,ran,ind*2+1,mid+1,r);
}
pair < int , int > query(int qp , int ind=1 , int l=0 , int r=N){
    push(ind,l,r);
    if(l == r)return tree[ind];
    int mid = (l + r) / 2;
    if(qp <= mid)return query(qp,ind*2,l,mid);
    else return query(qp,ind*2+1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    init();
    for(int i = 0;i<n;i++)update(i,i,{0,0});

    // cout << "segt : "<<endl;
    // for(int j = 0;j<n;j++){
    //     auto bruh = query(j);
    //     cout << bruh.first << " ";
    // }
    // cout << endl;
    // cout << endl;
    for(int i = 0;i<k;i++){
        // cout << "update : " << op[i] << " " << left[i] << " " << right[i] << " " << height[i] << endl;
        if(op[i] == 1){// height , inf
            update(left[i] , right[i] , {height[i] , inf});
        }
        else{// 0 , height
            update(left[i] , right[i] , {0 , height[i]});
        }
        // cout << "segt : "<<endl;
        // for(int j = 0;j<n;j++){
        //     auto bruh = query(j);
        //     cout << bruh.first << "," << bruh.second << "   ";
        // }
        // cout << endl;
        // cout << endl;
    }
    for(int i = 0;i<n;i++){
        finalHeight[i] = query(i).first;
    }
}

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