Submission #581487

#	Time	Username	Problem	Language	Result	Execution time	Memory
581487		jasmin	Wall (IOI14_wall)	C++17	32 / 100	888 ms	43172 KiB

wall

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

const int inf=1e9;

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<pair<int,int> > > add1(n);
    vector<vector<pair<int,int> > >add2(n);
    vector<vector<pair<int,int> > > sub1(n);
    vector<vector<pair<int,int> > > sub2(n);
    for(int i=0; i<k; i++){
        if(op[i]==1){
            add1[left[i]].push_back({hight[i], i});
            add2[right[i]].push_back({hight[i], i});
        }
        else{
            sub1[left[i]].push_back({hight[i], i});
            sub2[right[i]].push_back({hight[i], i});
        }
    }

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

        int h=0;
        if(!active.empty()){
            h=(*prev(active.end())).first;
        }
        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=inf;
        if(!active.empty()){
            h=(*active.begin()).first;
        }
        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);
        return;
    }
    buildWall2(n, k, op, left, right, hight, finalHight);
}

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

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