oj.uz

Submission #410666

# Submission time Handle Problem Language Result Execution time Memory
410666 2021-05-23T09:14:15 Z Haruto810198 Wall (IOI14_wall) C++17
100 / 100
 1465 ms 102492 KB 
#include "wall.h"
#include <algorithm>

using namespace std;

//#define int long long

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))

#define V st[cidx]
#define LC st[cidx*2]
#define RC st[cidx*2+1]

const int INF = 2147483647;
const int MAX = 2000010;

struct Node{
    int sl, sr;
    int tagl, tagr;
};

Node st[4*MAX];

void build(int cidx, int cl, int cr){
    V.sl = cl;
    V.sr = cr;
    V.tagl = 0;
    V.tagr = 0;
    if(cl < cr){
        int mid = (cl + cr) / 2;
        build(cidx*2, cl, mid);
        build(cidx*2+1, mid+1, cr);
    }
}

void addtag(int cidx, int mmin, int mmax){
    if(mmin > V.tagr){
        V.tagl = V.tagr = mmin;
    }
    else if(mmax < V.tagl){
        V.tagl = V.tagr = mmax;
    }
    else{
        V.tagl = max(V.tagl, mmin);
        V.tagr = min(V.tagr, mmax);
    }
}

void pushtag(int cidx){
    if(V.sl < V.sr){
        addtag(cidx*2, V.tagl, V.tagr);
        addtag(cidx*2+1, V.tagl, V.tagr);
    }
    V.tagl = -INF;
    V.tagr = INF;
}

void modify(int cidx, int ml, int mr, int mmin, int mmax){
    if(mr<V.sl or V.sr<ml){
        return;
    }
    else if(ml<=V.sl and V.sr<=mr){
        addtag(cidx, mmin, mmax);
        return;
    }
    else{
        pushtag(cidx);
        modify(cidx*2, ml, mr, mmin, mmax);
        modify(cidx*2+1, ml, mr, mmin, mmax);
    }
}

int query(int cidx, int qidx){
    if(V.sl==qidx and V.sr==qidx){
        return V.tagl;
    }
    else{
        pushtag(cidx);
        int mid = (V.sl + V.sr) / 2;
        if(qidx <= mid){
            return query(cidx*2, qidx);
        }
        else{
            return query(cidx*2+1, qidx);
        }
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    build(1, 0, n-1);

    FOR(i,0,k-1,1){
        if(op[i]==1){ /// Max
            modify(1, left[i], right[i], height[i], INF);
        }
        else if(op[i]==2){ /// min
            modify(1, left[i], right[i], -INF, height[i]);
        }
    }

    FOR(i,0,n-1,1){
        finalHeight[i] = query(1, i);
    }

}

Subtask #1
8.0 / 8.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 10 ms 1000 KB Output is correct
5 Correct 8 ms 996 KB Output is correct
6 Correct 8 ms 928 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 155 ms 13924 KB Output is correct
3 Correct 230 ms 8468 KB Output is correct
4 Correct 597 ms 22332 KB Output is correct
5 Correct 403 ms 23400 KB Output is correct
6 Correct 394 ms 21884 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 12 ms 972 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 159 ms 13832 KB Output is correct
9 Correct 201 ms 8384 KB Output is correct
10 Correct 587 ms 22296 KB Output is correct
11 Correct 397 ms 23424 KB Output is correct
12 Correct 396 ms 21960 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 162 ms 13868 KB Output is correct
15 Correct 41 ms 2408 KB Output is correct
16 Correct 726 ms 22644 KB Output is correct
17 Correct 392 ms 21976 KB Output is correct
18 Correct 400 ms 22024 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 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 996 KB Output is correct
5 Correct 10 ms 972 KB Output is correct
6 Correct 8 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 154 ms 13836 KB Output is correct
9 Correct 209 ms 8412 KB Output is correct
10 Correct 630 ms 22384 KB Output is correct
11 Correct 415 ms 23480 KB Output is correct
12 Correct 390 ms 21968 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 171 ms 13880 KB Output is correct
15 Correct 41 ms 2400 KB Output is correct
16 Correct 750 ms 22640 KB Output is correct
17 Correct 393 ms 22176 KB Output is correct
18 Correct 414 ms 22084 KB Output is correct
19 Correct 1427 ms 102388 KB Output is correct
20 Correct 1465 ms 99788 KB Output is correct
21 Correct 1416 ms 102324 KB Output is correct
22 Correct 1417 ms 99852 KB Output is correct
23 Correct 1401 ms 99812 KB Output is correct
24 Correct 1421 ms 99832 KB Output is correct
25 Correct 1407 ms 99696 KB Output is correct
26 Correct 1424 ms 102492 KB Output is correct
27 Correct 1415 ms 102304 KB Output is correct
28 Correct 1392 ms 99976 KB Output is correct
29 Correct 1397 ms 99764 KB Output is correct
30 Correct 1400 ms 99780 KB Output is correct