oj.uz

Submission #1062867

# Submission time Handle Problem Language Result Execution time Memory
1062867 2024-08-17T11:22:23 Z oscar1f Wall (IOI14_wall) C++17
100 / 100
 1091 ms 91988 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;

struct som {
    int debInter,finInter,minInter,maxInter;
};

const int TAILLE_MAX=(1<<21),INFINI=1000*1000*1000;
int nbVal,nbReq;
som lazy[2*TAILLE_MAX];

void pushFlag(int pos) {
    if (lazy[pos].debInter!=lazy[pos].finInter) {
        for (int j=0;j<2;j++) {
            if (lazy[2*pos+j].maxInter<lazy[pos].minInter) {
                lazy[2*pos+j].minInter=lazy[pos].minInter;
                lazy[2*pos+j].maxInter=lazy[pos].minInter;
            }
            else if (lazy[2*pos+j].minInter>lazy[pos].maxInter) {
                lazy[2*pos+j].minInter=lazy[pos].maxInter;
                lazy[2*pos+j].maxInter=lazy[pos].maxInter;
            }
            else {
                lazy[2*pos+j].minInter=max(lazy[2*pos+j].minInter,lazy[pos].minInter);
                lazy[2*pos+j].maxInter=min(lazy[2*pos+j].maxInter,lazy[pos].maxInter);
            }
        }
        lazy[pos].minInter=0;
        lazy[pos].maxInter=INFINI;
    }
}

void init(int pos,int deb,int fin) {
    lazy[pos].debInter=deb;
    lazy[pos].finInter=fin;
    //cout<<pos<<" "<<deb<<" "<<fin<<endl;
    if (deb!=fin) {
        int mid=(deb+fin)/2;
        init(2*pos,deb,mid);
        init(2*pos+1,mid+1,fin);
    }
}

void modif(int pos,int deb,int fin,int typeModif,int valModif) {
    if (lazy[pos].debInter>fin or lazy[pos].finInter<deb) {
        pushFlag(pos);
    }
    else if (lazy[pos].debInter>=deb and lazy[pos].finInter<=fin) {
        if (typeModif==1) {
            lazy[pos].minInter=max(lazy[pos].minInter,valModif);
            lazy[pos].maxInter=max(lazy[pos].maxInter,valModif);
        }
        else {
            lazy[pos].minInter=min(lazy[pos].minInter,valModif);
            lazy[pos].maxInter=min(lazy[pos].maxInter,valModif);
        }
        pushFlag(pos);
    }
    else {
        pushFlag(pos);
        if (lazy[pos].debInter!=lazy[pos].finInter) {
            modif(2*pos,deb,fin,typeModif,valModif);
            modif(2*pos+1,deb,fin,typeModif,valModif);
        }
    }
}

int calcVal(int pos,int posVal) {
    pushFlag(pos);
    if (lazy[pos].debInter<=posVal and lazy[pos].finInter>=posVal) {
        if (lazy[pos].debInter!=lazy[pos].finInter) {
            return calcVal(2*pos,posVal)+calcVal(2*pos+1,posVal);
        }
        else {
            return lazy[pos].minInter;
        }
    }
    else {
        return 0;
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    nbVal=n;
    nbReq=k;
    init(1,0,nbVal-1);
    for (int i=0;i<nbReq;i++) {
        modif(1,left[i],right[i],op[i],height[i]);
        /*for (int j=0;j<nbVal;j++) {
            cout<<calcVal(1,j)<<" ";
        }
        cout<<endl;*/
    }
    for (int i=0;i<nbVal;i++) {
        finalHeight[i]=calcVal(1,i);
    }
    return;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 84 ms 8156 KB Output is correct
3 Correct 132 ms 4688 KB Output is correct
4 Correct 394 ms 12892 KB Output is correct
5 Correct 235 ms 13652 KB Output is correct
6 Correct 239 ms 13452 KB Output is correct

Subtask #3
29.0 / 29.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 6 ms 1068 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1112 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 81 ms 8232 KB Output is correct
9 Correct 134 ms 4692 KB Output is correct
10 Correct 399 ms 12752 KB Output is correct
11 Correct 241 ms 13392 KB Output is correct
12 Correct 255 ms 13384 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 80 ms 8180 KB Output is correct
15 Correct 28 ms 1880 KB Output is correct
16 Correct 483 ms 13144 KB Output is correct
17 Correct 237 ms 13136 KB Output is correct
18 Correct 258 ms 13140 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 524 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1072 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 1076 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 77 ms 8232 KB Output is correct
9 Correct 143 ms 4776 KB Output is correct
10 Correct 444 ms 12884 KB Output is correct
11 Correct 233 ms 13436 KB Output is correct
12 Correct 237 ms 13436 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 82 ms 8144 KB Output is correct
15 Correct 28 ms 1880 KB Output is correct
16 Correct 489 ms 13140 KB Output is correct
17 Correct 241 ms 13180 KB Output is correct
18 Correct 238 ms 13140 KB Output is correct
19 Correct 1072 ms 91968 KB Output is correct
20 Correct 1065 ms 89516 KB Output is correct
21 Correct 1063 ms 91824 KB Output is correct
22 Correct 1035 ms 89448 KB Output is correct
23 Correct 1091 ms 89424 KB Output is correct
24 Correct 1038 ms 89428 KB Output is correct
25 Correct 1082 ms 89288 KB Output is correct
26 Correct 1039 ms 91920 KB Output is correct
27 Correct 1049 ms 91988 KB Output is correct
28 Correct 1057 ms 89464 KB Output is correct
29 Correct 1063 ms 89552 KB Output is correct
30 Correct 1046 ms 89428 KB Output is correct