oj.uz

Submission #568214

# Submission time Handle Problem Language Result Execution time Memory
568214 2022-05-24T23:05:26 Z losmi247 Wall (IOI14_wall) C++14
100 / 100
 1062 ms 169828 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6+4;
const int inf = 1e9;

int n,k;
int tp[N],levo[N],desno[N],vis[N];

struct sta{
    int mx,mn; /// maximise from below, minimise from above
} drvo[4*N],lazy[4*N];

sta spojimx(sta a,int maks){
    if(a.mx <= a.mn){
        if(maks <= a.mx) return a;
        else if(maks > a.mx && maks <= a.mn) return {maks,a.mn};
        else return {maks,maks};
    }
    else{
        if(maks <= a.mn) return a;
        else return {maks,maks};
    }
}

sta spojimn(sta a,int mini){
    return {a.mx,min(a.mn,mini)};
}

sta spoji(sta a,sta b){
    return spojimn(spojimx(a,b.mx),b.mn);
}

void push(int i,int j,int node){
    if(lazy[node].mx != 0 || lazy[node].mn != inf){
        //cout << "radim " << i << " " << j << " " << node << " " << lazy[node].mx << " " << lazy[node].mn << endl;
        if(i == j){
            //cout << "spajam " << drvo[node].mx << " " << drvo[node].mn << " sa " << lazy[node].mx << " " << lazy[node].mn << " dobijam ";
            drvo[node] = spoji(drvo[node],lazy[node]);
            //cout << drvo[node].mx << " " << drvo[node].mn << endl;
        }
        if(i != j){
            //cout << "ostalo od pre " << lazy[2*node].mx << " " << lazy[2*node].mn << endl;
            lazy[2*node] = spoji(lazy[2*node],lazy[node]);
            /*cout << "postaje " << lazy[2*node].mx << " " << lazy[2*node].mn << endl;
            cout << "ostalo od pre " << lazy[2*node+1].mx << " " << lazy[2*node+1].mn << endl;*/
            lazy[2*node+1] = spoji(lazy[2*node+1],lazy[node]);
            //cout << "postaje " << lazy[2*node+1].mx << " " << lazy[2*node+1].mn << endl;
        }
        lazy[node] = {0,inf};
    }
}

void update(int i,int j,int l,int r,sta val,int node){
    push(i,j,node);
    if(j < l || i > r) return;
    if(l <= i && r >= j){
        lazy[node] = val;
        push(i,j,node);
        return;
    }
    int mid = i+(j-i)/2;
    update(i,mid,l,r,val,2*node);
    update(mid+1,j,l,r,val,2*node+1);
}

sta daj(int pos){
    int i = 1,j = n,node = 1;
    while(i != j){
        push(i,j,node);
        int mid = i+(j-i)/2;
        if(pos <= mid){
            node *= 2;
            j = mid;
        }
        else{
            node *= 2;
            node++;
            i = mid+1;
        }
    }
    push(i,j,node);
    return drvo[node];
}

void buildWall(int br1,int br2,int op[],int left[],int right[],int height[],int finalHeight[]){
    n = br1;
    k = br2;
    for(int i = 0; i < k; i++){
        tp[i+1] = op[i];
        levo[i+1] = left[i]+1;
        desno[i+1] = right[i]+1;
        vis[i+1] = height[i];
    }

    for(int i = 0; i <= 4*n; i++){
        drvo[i] = {0,inf};
        lazy[i] = {0,inf};
    }

    for(int i = 1; i <= k; i++){
        if(tp[i] == 1){ /// maximise from below
            update(1,n,levo[i],desno[i],{vis[i],inf},1);
        }
        else{ /// minimise from above
            update(1,n,levo[i],desno[i],{0,vis[i]},1);
        }

        /*vector <pair<int,int>> h;
        for(int j = 1; j <= n; j++){
            sta x = daj(j);
            h.push_back({x.mx,x.mn});
        }
        for(auto f : h) cout << f.first << " " << f.second << "  ";
        cout << endl << endl;*/
    }

    for(int i = 1; i <= n; i++){
        sta x = daj(i);
        finalHeight[i-1] = min(x.mn,x.mx);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 368 KB Output is correct
4 Correct 10 ms 1236 KB Output is correct
5 Correct 7 ms 1220 KB Output is correct
6 Correct 6 ms 1276 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 176 ms 21772 KB Output is correct
3 Correct 237 ms 11824 KB Output is correct
4 Correct 675 ms 32388 KB Output is correct
5 Correct 321 ms 33488 KB Output is correct
6 Correct 290 ms 31948 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 9 ms 1292 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 6 ms 1236 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 139 ms 21788 KB Output is correct
9 Correct 219 ms 11856 KB Output is correct
10 Correct 663 ms 32392 KB Output is correct
11 Correct 286 ms 33484 KB Output is correct
12 Correct 312 ms 31888 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 145 ms 21716 KB Output is correct
15 Correct 47 ms 3080 KB Output is correct
16 Correct 853 ms 32640 KB Output is correct
17 Correct 328 ms 32064 KB Output is correct
18 Correct 292 ms 32068 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 3 ms 452 KB Output is correct
4 Correct 10 ms 1236 KB Output is correct
5 Correct 7 ms 1216 KB Output is correct
6 Correct 6 ms 1284 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 140 ms 21736 KB Output is correct
9 Correct 250 ms 11852 KB Output is correct
10 Correct 613 ms 32388 KB Output is correct
11 Correct 312 ms 33408 KB Output is correct
12 Correct 314 ms 31880 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 157 ms 21800 KB Output is correct
15 Correct 44 ms 3084 KB Output is correct
16 Correct 894 ms 32640 KB Output is correct
17 Correct 325 ms 32072 KB Output is correct
18 Correct 323 ms 32040 KB Output is correct
19 Correct 1008 ms 169772 KB Output is correct
20 Correct 960 ms 167316 KB Output is correct
21 Correct 1027 ms 169776 KB Output is correct
22 Correct 1016 ms 167256 KB Output is correct
23 Correct 1062 ms 167192 KB Output is correct
24 Correct 1000 ms 167316 KB Output is correct
25 Correct 1000 ms 167176 KB Output is correct
26 Correct 1034 ms 169756 KB Output is correct
27 Correct 943 ms 169828 KB Output is correct
28 Correct 998 ms 167344 KB Output is correct
29 Correct 992 ms 167188 KB Output is correct
30 Correct 945 ms 167292 KB Output is correct