Submission #1313993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313993		coderg	Wall (IOI14_wall)	C++20	100 / 100	350 ms	59188 KiB

wall

#include "bits/stdc++.h"
#include "wall.h"
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FR(i,l,r) for(int i=(l);i>=(r);--i)
typedef long long ll;

const int maxn=5000;
const int mod=1e9+7;
const int mox=2000*500+505;
const int inf=1e9;

//this solution was wrote like 5 hours ago
//I forgot to submit it :(
struct Node{
    int lb,ub;//lower_bound,upper_bound
};

vector<Node> tree;
int siz;

void apply_tag(int idx,int nlb,int nub){
    //maximize,height must be at least nlb
    tree[idx].lb=max(tree[idx].lb,nlb);
    tree[idx].ub=max(tree[idx].ub,nlb);
    //minimize,height must be at least nlb
    tree[idx].lb=min(tree[idx].lb,nub);
    tree[idx].ub=min(tree[idx].ub,nub);
}

void push(int idx){
    if(tree[idx].lb==0 && tree[idx].ub==inf)return;
    apply_tag(idx<<1,tree[idx].lb,tree[idx].ub);
    apply_tag(idx<<1|1,tree[idx].lb,tree[idx].ub);
    tree[idx].lb=0;
    tree[idx].ub=inf;
}

void update(int idx,int l,int r,int ql,int qr,int op,int h){
    if(ql<=l && r<=qr){
        if(op==1)apply_tag(idx,h,inf);
        else apply_tag(idx,0,h);
        return;
    }
    push(idx);
    int mid=l+(r-l)/2;
    if(ql<=mid)update(idx<<1,l,mid,ql,qr,op,h);
    if(qr>mid)update(idx<<1|1,mid+1,r,ql,qr,op,h);
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    siz=1;
    while(siz<n)siz<<=1;
    tree.assign(2*siz,{0,inf});
    F(i,0,k)update(1,0,siz-1,left[i],right[i],op[i],height[i]);
    F(i,1,siz)push(i);
    F(i,0,n)finalHeight[i]=tree[siz+i].lb;
}

Compilation message (stderr)

wall.cpp: In function 'void setIO(std::string)':
wall.cpp:11:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:11:98: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
      |                                                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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