oj.uz

Submission #779131

# Submission time Handle Problem Language Result Execution time Memory
779131 2023-07-11T08:13:05 Z fatemetmhr Wall (IOI14_wall) C++17
61 / 100
 562 ms 35824 KB 
//  ~ Be Name Khoda ~  //

#include "wall.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  8e6   + 10;
const int maxn5 =  2e6   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

void upd(int, int, int, int, int, int, int);

int ret[maxn5], segl[maxnt], segr[maxnt];

void shift(int l, int mid, int r, int v){
    upd(l, mid, l, mid, 1, segl[v], v * 2);
    upd(l, mid, l, mid, 2, segr[v], v * 2);
    upd(mid, r, mid, r, 1, segl[v], v * 2 + 1);
    upd(mid, r, mid, r, 2, segr[v], v * 2 + 1);
    segl[v] = 0;
    segr[v] = mod;
}

void upd(int l, int r, int lq, int rq, int ty, int k, int v){
    if(rq <= l || r <= lq)
        return;
    if(lq <= l && r <= rq){
        if(ty == 1){
            segl[v] = max(segl[v], k);
            segr[v] = max(segr[v], segl[v]);
        }
        else{
            segr[v] = min(segr[v], k);
            segl[v] = min(segl[v], segr[v]);
        }
        return;
    }
    int mid = (l + r) >> 1; shift(l, mid, r, v);
    upd(l, mid, lq, rq, ty, k, v * 2);
    upd(mid, r, lq, rq, ty, k, v * 2 + 1);
}

void shift_all(int l, int r, int v){
    if(r - l == 1){
        ret[l] = segl[v];
        return;
    }
    int mid = (l + r) >> 1;
    shift(l, mid, r, v);
    shift_all(l, mid, v * 2);
    shift_all(mid, r, v * 2 + 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    fill(segl, segl + maxnt, 0);
    fill(segr, segr + maxnt, mod);
    for(int i = 0; i < k; i++)
        upd(0, n, left[i], right[i] + 1, op[i], height[i], 1);
    shift_all(0, n, 1);
    for(int i = 0; i < n; i++)
        finalHeight[i] = ret[i];
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 10 ms 10004 KB Output is correct
5 Correct 9 ms 9936 KB Output is correct
6 Correct 9 ms 9904 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 134 ms 18800 KB Output is correct
3 Correct 199 ms 14416 KB Output is correct
4 Correct 551 ms 19144 KB Output is correct
5 Correct 367 ms 19488 KB Output is correct
6 Correct 349 ms 19452 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 7 ms 9784 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 10 ms 9956 KB Output is correct
5 Correct 10 ms 9904 KB Output is correct
6 Correct 9 ms 9904 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 120 ms 17960 KB Output is correct
9 Correct 192 ms 13652 KB Output is correct
10 Correct 547 ms 19032 KB Output is correct
11 Correct 349 ms 19524 KB Output is correct
12 Correct 385 ms 19456 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 121 ms 18000 KB Output is correct
15 Correct 34 ms 10888 KB Output is correct
16 Correct 544 ms 19208 KB Output is correct
17 Correct 359 ms 19200 KB Output is correct
18 Correct 393 ms 19204 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9792 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 10 ms 9940 KB Output is correct
5 Correct 9 ms 9920 KB Output is correct
6 Correct 12 ms 9908 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 117 ms 17956 KB Output is correct
9 Correct 194 ms 13640 KB Output is correct
10 Correct 546 ms 18968 KB Output is correct
11 Correct 356 ms 19408 KB Output is correct
12 Correct 352 ms 19576 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 118 ms 17964 KB Output is correct
15 Correct 34 ms 10832 KB Output is correct
16 Correct 562 ms 19176 KB Output is correct
17 Correct 366 ms 19236 KB Output is correct
18 Correct 349 ms 19196 KB Output is correct
19 Runtime error 144 ms 35824 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -