oj.uz

Submission #1009331

# Submission time Handle Problem Language Result Execution time Memory
1009331 2024-06-27T11:34:29 Z Muhammet Wall (IOI14_wall) C++17
61 / 100
 408 ms 24660 KB 
#include <bits/stdc++.h>
#include "wall.h"

#define ll long long
#define ff first
#define ss second
#define sz(s) (int)s.size()

using namespace std;

const ll N = 2000100;

pair<int,int> st[N];

vector <int> v;

void lz(int nd){
    if(nd * 2 < N){
        st[nd*2].ff = min(st[nd].ss,st[nd*2].ff);
        st[nd*2].ff = max(st[nd].ff,st[nd*2].ff);
        st[nd*2].ss = min(st[nd].ss,st[nd*2].ss);
        st[nd*2].ss = max(st[nd].ff,st[nd*2].ss);
    }
    if(nd * 2 + 1 < N){
        st[nd*2+1].ff = min(st[nd].ss,st[nd*2+1].ff);
        st[nd*2+1].ff = max(st[nd].ff,st[nd*2+1].ff);
        st[nd*2+1].ss = min(st[nd].ss,st[nd*2+1].ss);
        st[nd*2+1].ss = max(st[nd].ff,st[nd*2+1].ss);
    }
    return;
}

void upd(int nd, int l, int r, int x, int y, int h, int t){
    lz(nd);
    if(l > y or r < x) return;
    if(l >= x and r <= y){
        if(t == 1){
            st[nd].ff = max(st[nd].ff,h);
            st[nd].ss = max(st[nd].ss,h);
        }
        else {
            st[nd].ff = min(st[nd].ff,h);
            st[nd].ss = min(st[nd].ss,h);
        }
        return;
    }
    st[nd].ff = -1e9;
    st[nd].ss = 1e9;
    int md = (l + r) / 2;
    upd(nd*2,l,md,x,y,h,t);
    upd(nd*2+1,md+1,r,x,y,h,t);
}

void fnd(int nd, int l, int r){
    lz(nd);
    if(l == r){
        v.push_back(st[nd].ff);
        return;
    }
    int md = (l + r) / 2;
    fnd(nd*2, l, md);
    fnd(nd*2+1, md+1, r);
}

void buildWall(int n, int k, int t[], int l[], int r[], int h[], int a[]){
    for(int i = 0; i < k; i++){
        upd(1,0,n-1,l[i],r[i],h[i],t[i]);
    }
    fnd(1,0,n-1);
    for(int i = 0; i < n; i++){
        a[i] = v[i];
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1156 KB Output is correct
5 Correct 4 ms 1160 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 86 ms 12852 KB Output is correct
3 Correct 125 ms 8016 KB Output is correct
4 Correct 368 ms 20992 KB Output is correct
5 Correct 225 ms 21704 KB Output is correct
6 Correct 245 ms 20788 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 524 KB Output is correct
4 Correct 4 ms 1112 KB Output is correct
5 Correct 4 ms 1228 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 12748 KB Output is correct
9 Correct 129 ms 8016 KB Output is correct
10 Correct 403 ms 20936 KB Output is correct
11 Correct 229 ms 21704 KB Output is correct
12 Correct 217 ms 20680 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 90 ms 12816 KB Output is correct
15 Correct 21 ms 2644 KB Output is correct
16 Correct 408 ms 21432 KB Output is correct
17 Correct 231 ms 20684 KB Output is correct
18 Correct 247 ms 20812 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 1 ms 528 KB Output is correct
4 Correct 4 ms 1164 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 83 ms 12960 KB Output is correct
9 Correct 127 ms 8040 KB Output is correct
10 Correct 397 ms 21104 KB Output is correct
11 Correct 226 ms 21700 KB Output is correct
12 Correct 231 ms 20884 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 85 ms 12824 KB Output is correct
15 Correct 20 ms 2648 KB Output is correct
16 Correct 346 ms 21384 KB Output is correct
17 Correct 224 ms 20680 KB Output is correct
18 Correct 231 ms 20776 KB Output is correct
19 Runtime error 123 ms 24660 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -