oj.uz

Submission #879705

# Submission time Handle Problem Language Result Execution time Memory
879705 2023-11-27T23:46:26 Z AlphaMale06 Wall (IOI14_wall) C++14
100 / 100
 880 ms 102228 KB 
#include<bits/stdc++.h>

#include "wall.h"
using namespace std;
const int N = 2e6+3;
int mn[4*N], mx[4*N], f[4*N];
int inf=100000001;

void inter(int a, int b, int c, int d, int &lft, int &rgt){
    if(a>d){
        lft=rgt=a;
    }
    else if(b<c){
        lft=rgt=b;
    }
    else{
        lft=max(a, c);
        rgt=min(b, d);
    }
}

void Push(int node){
    int lc=2*node+1;
    int rc=2*node+2;
    inter(mx[node], mn[node], mx[lc], mn[lc], mx[lc], mn[lc]);
    inter(mx[node], mn[node], mx[rc], mn[rc], mx[rc], mn[rc]);
    f[lc]=f[rc]=f[node];
    mn[node]=inf;
    mx[node]=0;
}

void mxUpd(int node, int l, int r, int L, int R, int val){
    if(l>r || l>R | r<L)return;
    if(l>=L && r<=R){
        inter(val, inf, mx[node], mn[node], mx[node], mn[node]);
        if(mn[node]==inf)f[node]=0;
        else f[node]=1;
        return;
    }
    Push(node);
    int mid=(l+r)/2;
    mxUpd(2*node+1, l, mid, L, R, val);
    mxUpd(2*node+2, mid+1, r, L, R, val);
}

void mnUpd(int node, int l, int r, int L, int R, int val){
    if(l>r || l>R || r<L)return;
    if(l>=L && r<=R){
        inter(0, val, mx[node], mn[node], mx[node], mn[node]);
        if(mx[node]==0)f[node]=1;
        else f[node]=0;
        return;
    }
    Push(node);
    int mid=(l+r)/2;
    mnUpd(2*node+1, l, mid, L, R, val);
    mnUpd(2*node+2, mid+1, r, L, R, val);
}
int Get(int node, int l, int r, int ind){
    if(l>ind || r<ind)return 0;
    if(l==r){
        if(f[node])return max(mx[node], mn[node]);
        else return min(mn[node], mx[node]);
    }
    Push(node);
    int mid=(l+r)/2;
    return Get(2*node+1, l, mid, ind)+Get(2*node+2, mid+1, r, ind);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=0; i<4*N; i++)mn[i]=inf;
    for(int i=0; i< k; i++){
        if(op[i]==1){
            mxUpd(0, 0, n-1, left[i], right[i], height[i]);
        }
        else{
            mnUpd(0, 0, n-1, left[i], right[i], height[i]);
        }
    }
    for(int i=0; i< n; i++){
        finalHeight[i]=Get(0, 0, n-1, i);
    }
    return;
}

Compilation message

wall.cpp: In function 'void mxUpd(int, int, int, int, int, int)':
wall.cpp:33:16: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   33 |     if(l>r || l>R | r<L)return;
      |               ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32604 KB Output is correct
2 Correct 9 ms 32604 KB Output is correct
3 Correct 7 ms 32648 KB Output is correct
4 Correct 12 ms 32904 KB Output is correct
5 Correct 11 ms 33116 KB Output is correct
6 Correct 11 ms 33112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32600 KB Output is correct
2 Correct 127 ms 40472 KB Output is correct
3 Correct 132 ms 38480 KB Output is correct
4 Correct 370 ms 53840 KB Output is correct
5 Correct 230 ms 54896 KB Output is correct
6 Correct 233 ms 53340 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32604 KB Output is correct
2 Correct 7 ms 32556 KB Output is correct
3 Correct 7 ms 32604 KB Output is correct
4 Correct 12 ms 33116 KB Output is correct
5 Correct 11 ms 33116 KB Output is correct
6 Correct 11 ms 32936 KB Output is correct
7 Correct 7 ms 32604 KB Output is correct
8 Correct 133 ms 46176 KB Output is correct
9 Correct 132 ms 42260 KB Output is correct
10 Correct 363 ms 53844 KB Output is correct
11 Correct 236 ms 55008 KB Output is correct
12 Correct 227 ms 53264 KB Output is correct
13 Correct 6 ms 32600 KB Output is correct
14 Correct 120 ms 46164 KB Output is correct
15 Correct 34 ms 36188 KB Output is correct
16 Correct 467 ms 54068 KB Output is correct
17 Correct 255 ms 53516 KB Output is correct
18 Correct 238 ms 53520 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32600 KB Output is correct
2 Correct 8 ms 32604 KB Output is correct
3 Correct 7 ms 32500 KB Output is correct
4 Correct 12 ms 33112 KB Output is correct
5 Correct 15 ms 33136 KB Output is correct
6 Correct 11 ms 33116 KB Output is correct
7 Correct 6 ms 32604 KB Output is correct
8 Correct 116 ms 46056 KB Output is correct
9 Correct 131 ms 42044 KB Output is correct
10 Correct 375 ms 53840 KB Output is correct
11 Correct 257 ms 54748 KB Output is correct
12 Correct 266 ms 53488 KB Output is correct
13 Correct 6 ms 32604 KB Output is correct
14 Correct 119 ms 46192 KB Output is correct
15 Correct 34 ms 36180 KB Output is correct
16 Correct 486 ms 53984 KB Output is correct
17 Correct 243 ms 53584 KB Output is correct
18 Correct 257 ms 53584 KB Output is correct
19 Correct 880 ms 101948 KB Output is correct
20 Correct 866 ms 99452 KB Output is correct
21 Correct 869 ms 102012 KB Output is correct
22 Correct 826 ms 99384 KB Output is correct
23 Correct 872 ms 99492 KB Output is correct
24 Correct 831 ms 99372 KB Output is correct
25 Correct 865 ms 99428 KB Output is correct
26 Correct 838 ms 102228 KB Output is correct
27 Correct 868 ms 102080 KB Output is correct
28 Correct 821 ms 99488 KB Output is correct
29 Correct 829 ms 99512 KB Output is correct
30 Correct 838 ms 99680 KB Output is correct