oj.uz

Submission #581369

# Submission time Handle Problem Language Result Execution time Memory
581369 2022-06-22T14:28:22 Z wdjpng Wall (IOI14_wall) C++17
100 / 100
 1219 ms 162048 KB 
#include "wall.h"
#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
using namespace std;

struct s
{
    int minn = 0, maxx=1e15;
};

vector<s>T;
s def = s();
// s1 is new

int query(int i, int l, int r, int qi)
{
    if(l>qi||r<=qi) return -1;
    if(l+1==r) return i;
    return max(query(2*i,l,(l+r)/2,qi), query(2*i+1,(l+r)/2,r,qi));
}

void update(int i, int l, int r, int ul, int ur, bool add, int v)
{
    if(l>=ur||r<=ul) return;
    if(l>=ul&&r<=ur) {
        if(add) {
            T[i].minn=max(T[i].minn,v);
            T[i].maxx=max(T[i].maxx, v);
        }
        else { // cut down
            T[i].maxx=min(T[i].maxx, v); 
            T[i].minn=min(T[i].minn,v);
        }
        return;
    }
    
    if(T[i].minn!=def.minn||T[i].maxx!=def.maxx)
    {
        rep(j,2)
        {
            T[2*i+j].minn=max(T[2*i+j].minn,T[i].minn);
            T[2*i+j].maxx=max(T[2*i+j].maxx,T[i].minn);
            T[2*i+j].maxx=min(T[2*i+j].maxx,T[i].maxx); 
            T[2*i+j].minn=min(T[2*i+j].minn,T[i].maxx);
        }
        T[i]=def;
    }
    update(2*i,l,(l+r)/2,ul,ur,add,v);
    update(2*i+1,(l+r)/2,r,ul,ur,add,v);
}

void buildWall(signed n, signed k, signed op[], signed left[], signed right[], signed height[], signed finalHeight[]){
    T.assign(4*n+2,s());

    rep(ck,k)
    {
        update(1,0,n,left[ck],right[ck]+1,op[ck]==1,height[ck]);
    }

    rep(i,n) update(1,0,n,i,i+1,true,0);
    rep(i,n) finalHeight[i] = T[query(1,0,n,i)].minn;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 7 ms 1100 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 131 ms 8076 KB Output is correct
3 Correct 148 ms 4872 KB Output is correct
4 Correct 500 ms 24508 KB Output is correct
5 Correct 266 ms 25568 KB Output is correct
6 Correct 267 ms 23956 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 6 ms 980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 146 ms 8056 KB Output is correct
9 Correct 172 ms 4712 KB Output is correct
10 Correct 444 ms 24656 KB Output is correct
11 Correct 276 ms 25548 KB Output is correct
12 Correct 256 ms 24032 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 152 ms 13944 KB Output is correct
15 Correct 30 ms 2544 KB Output is correct
16 Correct 456 ms 24812 KB Output is correct
17 Correct 284 ms 24208 KB Output is correct
18 Correct 261 ms 24212 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 11 ms 1048 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Correct 7 ms 1048 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 143 ms 8336 KB Output is correct
9 Correct 160 ms 4748 KB Output is correct
10 Correct 436 ms 24508 KB Output is correct
11 Correct 268 ms 25596 KB Output is correct
12 Correct 332 ms 24160 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 143 ms 13880 KB Output is correct
15 Correct 38 ms 2476 KB Output is correct
16 Correct 444 ms 24908 KB Output is correct
17 Correct 270 ms 24284 KB Output is correct
18 Correct 265 ms 24244 KB Output is correct
19 Correct 1188 ms 161884 KB Output is correct
20 Correct 1168 ms 159348 KB Output is correct
21 Correct 1159 ms 162048 KB Output is correct
22 Correct 1173 ms 159344 KB Output is correct
23 Correct 1169 ms 159448 KB Output is correct
24 Correct 1179 ms 159536 KB Output is correct
25 Correct 1168 ms 159432 KB Output is correct
26 Correct 1170 ms 161888 KB Output is correct
27 Correct 1219 ms 161936 KB Output is correct
28 Correct 1204 ms 159504 KB Output is correct
29 Correct 1178 ms 159344 KB Output is correct
30 Correct 1160 ms 159436 KB Output is correct