oj.uz

Submission #1083647

# Submission time Handle Problem Language Result Execution time Memory
1083647 2024-09-03T17:43:22 Z MrPavlito Wall (IOI14_wall) C++17
100 / 100
 919 ms 169844 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 = 1e9+50;

vector<int> niz(MAXN,0);
vector<pii> seg(MAXN<<2);
vector<int> maxlazy(MAXN<<2,-inf);
vector<int> 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, seg[nod].sc);
        seg[nod].fi = max(seg[nod].fi, h);
        minlazy[nod] = max(minlazy[nod],h);
        maxlazy[nod] = max(maxlazy[nod],h);
        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, seg[nod].sc);
        seg[nod].fi = min(h, seg[nod].fi);
        minlazy[nod] = min(minlazy[nod],h);
        maxlazy[nod] = min(maxlazy[nod],h);
        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 57 ms 133280 KB Output is correct
2 Correct 54 ms 133592 KB Output is correct
3 Correct 54 ms 133456 KB Output is correct
4 Correct 58 ms 133712 KB Output is correct
5 Correct 71 ms 133656 KB Output is correct
6 Correct 56 ms 133716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 133460 KB Output is correct
2 Correct 138 ms 146992 KB Output is correct
3 Correct 190 ms 140624 KB Output is correct
4 Correct 461 ms 151352 KB Output is correct
5 Correct 284 ms 152536 KB Output is correct
6 Correct 280 ms 150864 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 133456 KB Output is correct
2 Correct 55 ms 133604 KB Output is correct
3 Correct 67 ms 133460 KB Output is correct
4 Correct 65 ms 133712 KB Output is correct
5 Correct 57 ms 133716 KB Output is correct
6 Correct 60 ms 133712 KB Output is correct
7 Correct 48 ms 133456 KB Output is correct
8 Correct 140 ms 147160 KB Output is correct
9 Correct 202 ms 140444 KB Output is correct
10 Correct 462 ms 151384 KB Output is correct
11 Correct 320 ms 152400 KB Output is correct
12 Correct 282 ms 150864 KB Output is correct
13 Correct 57 ms 133456 KB Output is correct
14 Correct 167 ms 147024 KB Output is correct
15 Correct 77 ms 134708 KB Output is correct
16 Correct 567 ms 151716 KB Output is correct
17 Correct 278 ms 151140 KB Output is correct
18 Correct 322 ms 151168 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 133392 KB Output is correct
2 Correct 55 ms 133456 KB Output is correct
3 Correct 50 ms 133456 KB Output is correct
4 Correct 56 ms 133672 KB Output is correct
5 Correct 55 ms 133672 KB Output is correct
6 Correct 60 ms 133768 KB Output is correct
7 Correct 55 ms 133492 KB Output is correct
8 Correct 135 ms 147028 KB Output is correct
9 Correct 188 ms 140520 KB Output is correct
10 Correct 443 ms 151376 KB Output is correct
11 Correct 272 ms 152368 KB Output is correct
12 Correct 268 ms 150944 KB Output is correct
13 Correct 50 ms 133344 KB Output is correct
14 Correct 128 ms 147024 KB Output is correct
15 Correct 82 ms 134480 KB Output is correct
16 Correct 495 ms 151636 KB Output is correct
17 Correct 287 ms 150992 KB Output is correct
18 Correct 273 ms 151124 KB Output is correct
19 Correct 919 ms 169696 KB Output is correct
20 Correct 794 ms 167248 KB Output is correct
21 Correct 895 ms 169828 KB Output is correct
22 Correct 824 ms 167200 KB Output is correct
23 Correct 847 ms 167188 KB Output is correct
24 Correct 885 ms 167252 KB Output is correct
25 Correct 845 ms 167208 KB Output is correct
26 Correct 855 ms 169844 KB Output is correct
27 Correct 838 ms 169812 KB Output is correct
28 Correct 850 ms 167248 KB Output is correct
29 Correct 834 ms 167268 KB Output is correct
30 Correct 815 ms 167248 KB Output is correct