제출 #581469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581469		jasmin	벽 (IOI14_wall)	C++17	0 / 100	1 ms	340 KiB

wall

#include<wall.h>
#include<bits/stdc++.h>
using namespace std;

void buildWallsmall(int n, int k, signed op[], signed left[], signed right[], 
            signed hight[], signed finalHight[]){

    for(int i=0; i<k; i++){

        for(int j=left[i]; j<=right[i]; j++){
            if(op[i]==1){
                finalHight[j]=max(finalHight[j], hight[i]);
            }
            else{
                finalHight[j]=min(finalHight[j], hight[i]);
            }
        }
    }
}
void buildWall2(int n, int k, signed op[], signed left[], signed right[], 
            signed hight[], signed finalHight[]){

    vector<vector<int> > add1;
    vector<vector<int> >add2;
    vector<vector<int> > sub1;
    vector<vector<int> > sub2;
    for(int i=0; i<k; i++){
        if(op[i]==1){
            add1[left[i]].push_back(hight[i]);
            add2[right[i]].push_back(hight[i]);
        }
        else{
            sub1[left[i]].push_back(hight[i]);
            sub2[left[i]].push_back(hight[i]);
        }
    }

    multiset<int> active;
    for(int i=0; i<n; i++){
        for(auto e: add1[i]){
            active.insert(e);
        }

        int h=*prev(active.end());
        finalHight[i]=h;

        for(auto e: add2[i]){
            active.erase(e);
        }
    }
    active.clear();
    for(int i=0; i<n; i++){
        for(auto e: sub1[i]){
            active.insert(e);
        }

        int h=*active.begin();
        finalHight[i]=min(finalHight[i], h);

        for(auto e: sub2[i]){
            active.erase(e);
        }
    }
}

void buildWall(int n, int k, signed op[], signed left[], signed right[], 
            signed hight[], signed finalHight[]){

    if(n<=(int)1e4){
        buildWallsmall(n, k, op, left, right, hight, finalHight);
    }
    buildWall2(n, k, op, left, right, hight, finalHight);
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39