oj.uz

Submission #409431

# Submission time Handle Problem Language Result Execution time Memory
409431 2021-05-20T17:48:25 Z MDario Wall (IOI14_wall) C++11
100 / 100
 1010 ms 107124 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
pair<int, int> st[8000001];
int r[2000001];
void lazy(ll xf, ll lf, ll rf){
    if(lf==rf)return;
    st[xf*2].F=min(st[xf*2].F, st[xf].S);
    st[xf*2].F=max(st[xf*2].F, st[xf].F);
    st[xf*2].S=max(st[xf*2].F, min(st[xf*2].S, st[xf].S));
    st[xf*2+1].F=min(st[xf*2+1].F, st[xf].S);
    st[xf*2+1].F=max(st[xf*2+1].F, st[xf].F);
    st[xf*2+1].S=max(st[xf*2+1].F, min(st[xf*2+1].S, st[xf].S));
    st[xf]={0, 1000000};
    return;
}
void update1(int xf, int lf, int rf, int ol, int od, int v){
    lazy(xf, lf, rf);
    if(rf<ol||lf>od)return;
    if(ol<=lf&&rf<=od){
        if(lf==rf){
            st[xf].F=max(st[xf].F, v);
            st[xf].S=max(st[xf].S, v);
            return;
        }
        st[xf].F=v;
        lazy(xf, lf, rf);
        return;
    }
    update1(xf*2, lf, (lf+rf)/2, ol, od, v);
    update1(xf*2+1, (lf+rf)/2+1, rf, ol, od, v);
    return ;
}
void update2(int xf, int lf, int rf, int ol, int od, int v){
    lazy(xf, lf, rf);
    if(rf<ol||lf>od)return;
    if(ol<=lf&&rf<=od){
        if(lf==rf){
            st[xf].F=min(st[xf].F, v);
            st[xf].S=min(st[xf].S, v);
            return;
        }
        st[xf].S=v;
        lazy(xf, lf, rf);
        return;
    }
    update2(xf*2, lf, (lf+rf)/2, ol, od, v);
    update2(xf*2+1, (lf+rf)/2+1, rf, ol, od, v);
    return ;
}
void rbuild(int xf, int lf, int rf){
    lazy(xf, lf, rf);
    if(lf==rf){
        r[lf]=st[xf].F;
        return;
    }
    rbuild(xf*2, lf, (lf+rf)/2);
    rbuild(xf*2+1, (lf+rf)/2+1, rf);
    return ;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=0; i<=4*n; i++)st[i].S=1000000;
    for(int i=0; i<k; i++){
        if(op[i]==1)update1(1, 1, n, left[i]+1, right[i]+1, height[i]);
        else update2(1, 1, n, left[i]+1, right[i]+1, height[i]);
    }
    rbuild(1, 1, n);
    for(int i=0; i<n; i++){
        finalHeight[i]=r[i+1];
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 7 ms 904 KB Output is correct
6 Correct 6 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 165 ms 13892 KB Output is correct
3 Correct 245 ms 8132 KB Output is correct
4 Correct 594 ms 21800 KB Output is correct
5 Correct 404 ms 22808 KB Output is correct
6 Correct 385 ms 21392 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 6 ms 844 KB Output is correct
6 Correct 6 ms 880 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 168 ms 14000 KB Output is correct
9 Correct 209 ms 8000 KB Output is correct
10 Correct 595 ms 21768 KB Output is correct
11 Correct 389 ms 22864 KB Output is correct
12 Correct 379 ms 21372 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 165 ms 13916 KB Output is correct
15 Correct 36 ms 2028 KB Output is correct
16 Correct 606 ms 22032 KB Output is correct
17 Correct 380 ms 21480 KB Output is correct
18 Correct 431 ms 21412 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 440 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 844 KB Output is correct
5 Correct 6 ms 824 KB Output is correct
6 Correct 6 ms 844 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 165 ms 13912 KB Output is correct
9 Correct 207 ms 8112 KB Output is correct
10 Correct 631 ms 21772 KB Output is correct
11 Correct 427 ms 22828 KB Output is correct
12 Correct 388 ms 21272 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 193 ms 13892 KB Output is correct
15 Correct 37 ms 2012 KB Output is correct
16 Correct 591 ms 22024 KB Output is correct
17 Correct 383 ms 21480 KB Output is correct
18 Correct 404 ms 21480 KB Output is correct
19 Correct 961 ms 107008 KB Output is correct
20 Correct 950 ms 104612 KB Output is correct
21 Correct 1010 ms 107084 KB Output is correct
22 Correct 923 ms 104616 KB Output is correct
23 Correct 963 ms 104620 KB Output is correct
24 Correct 937 ms 104540 KB Output is correct
25 Correct 945 ms 104656 KB Output is correct
26 Correct 968 ms 107096 KB Output is correct
27 Correct 928 ms 107124 KB Output is correct
28 Correct 942 ms 104492 KB Output is correct
29 Correct 926 ms 104648 KB Output is correct
30 Correct 929 ms 104700 KB Output is correct