Submission #1083646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083646		MrPavlito	Wall (IOI14_wall)	C++17	8 / 100	143 ms	262144 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 2e6+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;

vector<int> niz(MAXN,0);
vector<pair<long long,long long>> seg(MAXN<<2);
vector<long long> maxlazy(MAXN<<2,-inf);
vector<long long> minlazy(MAXN<<2,inf);


void addpush(int nod, int tl, int tr)
{
    if(tl == tr)return;
    if(maxlazy[nod] == -inf)return;
    maxlazy[nod<<1] = max(maxlazy[nod<<1], maxlazy[nod]);
    minlazy[nod<<1] = max(minlazy[nod<<1], maxlazy[nod]);
    maxlazy[nod<<1|1] = max(maxlazy[nod<<1|1], maxlazy[nod]);
    minlazy[nod<<1|1] = max(minlazy[nod<<1|1], maxlazy[nod]);
    seg[nod<<1].fi =  max(seg[nod<<1].fi, maxlazy[nod]);
    seg[nod<<1|1].fi =  max(seg[nod<<1|1].fi, maxlazy[nod]);
    seg[nod<<1].sc =  max(seg[nod<<1].sc, maxlazy[nod]);
    seg[nod<<1|1].sc =  max(seg[nod<<1|1].sc, maxlazy[nod]);
    maxlazy[nod] = -inf;
    //minlazy[nod] = inf;
}

void removepush(int nod, int tl, int tr)
{
    if(tl == tr)return;
    if(minlazy[nod] == inf)return;
    maxlazy[nod<<1] = min(maxlazy[nod<<1], minlazy[nod]);
    minlazy[nod<<1] = min(minlazy[nod<<1], minlazy[nod]);
    maxlazy[nod<<1|1] = min(maxlazy[nod<<1|1], minlazy[nod]);
    minlazy[nod<<1|1] = min(minlazy[nod<<1|1], minlazy[nod]);
    seg[nod<<1].fi =  min(seg[nod<<1].fi, minlazy[nod]);
    seg[nod<<1|1].fi =  min(seg[nod<<1|1].fi, minlazy[nod]);
    seg[nod<<1].sc =  min(seg[nod<<1].sc, minlazy[nod]);
    seg[nod<<1|1].sc =  min(seg[nod<<1|1].sc, minlazy[nod]);
    //maxlazy[nod] = -inf;
    minlazy[nod] = inf;
}

void push(int nod, int tl, int tr, bool mode)
{
    if(mode == 1)
    {
        removepush(nod, tl, tr);
        addpush(nod, tl, tr);
    }
    else
    {
        addpush(nod, tl, tr);
        removepush(nod, tl, tr);
    }
}

void addupdate(int nod, int tl, int tr, int l, int r, int h)
{
    if(tl> tr || tl>r || tr<l)return;
    if(tl>=l && tr<=r)
    {
        seg[nod].sc = max(h*1ll, seg[nod].sc);
        seg[nod].fi = max(seg[nod].fi, h*1ll);
        minlazy[nod] = max(minlazy[nod],h*1ll);
        maxlazy[nod] = max(maxlazy[nod],h*1ll);
        return;
    }
    push(nod, tl, tr, 2);
    int mid = tl+tr>>1;
    addupdate(nod<<1, tl, mid, l ,r, h);
    addupdate(nod<<1|1, mid+1, tr, l ,r, h);
    seg[nod].fi = max(seg[nod<<1].fi, seg[nod<<1|1].fi);
    seg[nod].sc = min(seg[nod<<1].sc, seg[nod<<1|1].sc);
}

void removeupdate(int nod, int tl, int tr, int l, int r, int h)
{

    if(tl> tr || tl>r || tr<l)return;
    if(tl>=l && tr<=r)
    {
        seg[nod].sc = min(h*1ll, seg[nod].sc);
        seg[nod].fi = min(h*1ll, seg[nod].fi);
        minlazy[nod] = min(minlazy[nod],h*1ll);
        maxlazy[nod] = min(maxlazy[nod],h*1ll);
        return;
    }
    push(nod, tl, tr, 1);
    int mid = tl+tr>>1;
    removeupdate(nod<<1, tl, mid, l ,r, h);
    removeupdate(nod<<1|1, mid+1, tr, l ,r, h);
    seg[nod].fi = max(seg[nod<<1].fi, seg[nod<<1|1].fi);
    seg[nod].sc = min(seg[nod<<1].sc, seg[nod<<1|1].sc);
}

int get(int nod, int tl, int tr, int index)
{
    push(nod, tl, tr, 1);
    if(tl == tr)return seg[nod].sc;
    int mid = tl+tr>>1;
    if(index<= mid)return get(nod<<1, tl, mid, index);
    else return get(nod<<1|1, mid+1, tr, index);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=0; i<k; i++)
    {
        if(op[i] == 1)addupdate(1,1,n,left[i]+1, right[i]+1,height[i]);
        else removeupdate(1,1,n,left[i]+1, right[i]+1,height[i]);
    }
    for(int i=0; i<n; i++)finalHeight[i] = get(1,1,n, i+1);
  return;
}

/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

Compilation message (stderr)

wall.cpp: In function 'void addupdate(int, int, int, int, int, int)':
wall.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = tl+tr>>1;
      |               ~~^~~
wall.cpp: In function 'void removeupdate(int, int, int, int, int, int)':
wall.cpp:102:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |     int mid = tl+tr>>1;
      |               ~~^~~
wall.cpp: In function 'int get(int, int, int, int)':
wall.cpp:113:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |     int mid = tl+tr>>1;
      |               ~~^~~

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