oj.uz

Submission #1083646

# Submission time Handle Problem Language Result Execution time Memory
1083646 2024-09-03T17:42:07 Z MrPavlito Wall (IOI14_wall) C++17
8 / 100
 143 ms 262144 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 258640 KB Output is correct
2 Correct 91 ms 258708 KB Output is correct
3 Correct 95 ms 258608 KB Output is correct
4 Correct 96 ms 258896 KB Output is correct
5 Correct 95 ms 258772 KB Output is correct
6 Correct 101 ms 258900 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 258568 KB Output is correct
2 Runtime error 134 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 258640 KB Output is correct
2 Correct 103 ms 258856 KB Output is correct
3 Correct 94 ms 258640 KB Output is correct
4 Correct 102 ms 258920 KB Output is correct
5 Correct 99 ms 258992 KB Output is correct
6 Correct 102 ms 258792 KB Output is correct
7 Correct 99 ms 258664 KB Output is correct
8 Runtime error 143 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 258644 KB Output is correct
2 Correct 92 ms 258640 KB Output is correct
3 Correct 87 ms 258732 KB Output is correct
4 Correct 98 ms 258832 KB Output is correct
5 Correct 99 ms 258900 KB Output is correct
6 Correct 101 ms 258972 KB Output is correct
7 Correct 91 ms 258652 KB Output is correct
8 Runtime error 137 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -