Submission #444386

#	Time	Username	Problem	Language	Result	Execution time	Memory
444386		FEDIKUS	Wall (IOI14_wall)	C++17	0 / 100	1 ms	204 KiB

wall

#include "wall.h"

#include<bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair

using namespace std;

typedef pair<int,int> pii;

const int maxn=2e6+10;
pii seg[4*maxn]; //xx je max(ai,k), yy je min(ai,k)
int n;

pii comb(pii a,pii b){
    if(b==mp(-1,-1)) return a;
    pii ret=mp(min(a.xx,b.xx),max(a.yy,b.yy));
    if(ret.xx<ret.yy){
        if(ret.xx==a.xx) ret.yy=a.xx;
        else ret.xx=a.yy;
    }
    return ret;
}

void push(int ind){
    seg[2*ind]=comb(seg[ind],seg[2*ind]);
    seg[2*ind+1]=comb(seg[ind],seg[2*ind+1]);
    seg[ind]=mp(-1,-1);
}

void update(int tl,int tr,int hg,int hd,int ind=1,int l=0,int r=n-1){
    if(l!=r) push(ind);
    if(tl<=l && r<=tr){
        seg[ind]=mp(hg,hd);
        return;
    }
    int mid=l+(r-l)/2;
    if(tl<=mid) update(tl,tr,hg,hd,2*ind,l,mid);
    if(tr>mid) update(tl,tr,hg,hd,2*ind+1,mid+1,r);
}

int query(int t,int ind=1,int l=0,int r=n-1){
    if(l!=r) push(ind);
    if(l==r){
        return seg[ind].xx;
    }
    int mid=l+(r-l)/2;
    if(t<=mid) return query(t,2*ind,l,mid);
    if(t>mid) return query(t,2*ind,mid+1,r);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N;
    for(int i=0;i<k;i++){
        if(op[i]==1){
            update(left[i],right[i],INT_MAX,height[i]);
        }else{
            update(left[i],right[i],height[i],INT_MIN);
        }
    }
    for(int i=0;i<n;i++) finalHeight[i]=query(i);
    return;
}

Compilation message (stderr)

wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
   51 | }
      | ^

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