Submission #1079457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079457		anton	Tiles (BOI24_tiles)	C++17	71 / 100	211 ms	25416 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pt complex<int>
#define pii pair<int, int>
int N, M;


struct Interval{
    int x;
    int yl, yr;
    bool open = false;

    bool operator<(const Interval& b)const{
        return yl<b.yl;
    }
    vector<Interval> clip(pii other_pair){
        //////cout<<"clipping "<<yl<<" "<<yr<<" "<<other_pair.first<<" "<<other_pair.second<<endl;

        if(yr<other_pair.first || other_pair.second<yl){
            return {*this};
        }
        if(yl<=other_pair.first && other_pair.second<=yr){
            return {Interval{x, yl, other_pair.first-1, open}, Interval{x, other_pair.second+1, yr, open}};
        }
        if(other_pair.first<= yl && yr<=other_pair.second){
            return {Interval{x, 0, -1, open}};
        }
        if(other_pair.first<=yl && other_pair.second<=yr){
            return {Interval{x, other_pair.second+1, yr, open}};
        }
        if(other_pair.first>=yl && other_pair.second>=yr){
            return {Interval{x, yl, other_pair.first-1, open}};
        }
        assert(false);
    }

    bool is_valid(){
        return yl<=yr;
    }

    int len() const{
        return yr-yl+1;
    }
};
Interval merge_inter(Interval a, Interval b){
    return Interval{a.x, a.yl, b.yr, true};
}
struct InterSet{
    set<Interval> intervals;
    bool is_valid = true;
    int nb_unpair= 0;
    
    void insert_small(Interval new_inter){
        if((new_inter.len())%2 ==1){
            nb_unpair++;
        }
        intervals.insert(new_inter);
    }
    std::set<Interval>::iterator erase(std::set<Interval>::iterator it){
        if(((*it).len())%2==1){
            nb_unpair--;
        }
        return intervals.erase(it);
    }
    std::set<Interval>::iterator merge(std::set<Interval>::iterator a, std::set<Interval>::iterator b){
        if(a->yr+1 == b->yl){
            Interval ia = *a;
            Interval ib = *b;
            erase(a);
            erase(b);
            Interval result =merge_inter(ia, ib);
            insert_small(result);
            return intervals.find(result);
        }
        return b;
    }
    void insert(Interval new_inter){
        insert_small(new_inter);
        auto it = intervals.find(new_inter);
        if(it!=intervals.begin()){
            auto prev= it;
            --prev;
            it = merge(prev, it);
        }
        auto next = it;
        next++;
        if(next!=intervals.end()){
            next = merge(it, next);
        }
    }
    
    
    void insert_big(Interval new_inter){
        //cout<<"inserting "<<new_inter.yl<<" "<<new_inter.yr<<endl;

        /*for(auto e: intervals){
            //cout<<e.yl<<" "<<e.yr<<endl;
        }*/
        auto lb = intervals.upper_bound(new_inter);
        if(lb!=intervals.begin()){
            --lb;
        }
        auto rb = intervals.upper_bound(Interval{0, new_inter.yr, new_inter.yr, false});
        if(rb!= intervals.end()){
            ++rb;
        }
            
        vector<Interval> to_insert;
        for(auto it = lb; it!= rb;){
            Interval val = *it;
            it = erase(it);
            vector<Interval>resulting =  val.clip({new_inter.yl, new_inter.yr});
            for(auto val2: resulting){
                if(!new_inter.open){
                    if(pii({val.yl, val.yr}) != pii({val2.yl, val2.yr})){
                        is_valid &= (new_inter.x-val.x)%2==0;
                    }
                }
                
                if(val2.is_valid()){
                    to_insert.push_back(val2);
                }
            }
        }

        for(auto e: to_insert){
            insert(e);
        }
        if(new_inter.open){
            insert(new_inter);
        }
    }
};

signed main(){
    cin>>N>>M;
    vector<pt> pts;
    for(int i = 0; i<N; i++){
        int a, b;
        cin>>a>>b;
        pts.push_back({a, b});
    }

    vector<pair<pt, pt>> edges;
    pt prev= pts.back();
    for(int i = 0; i<N; i++){
        edges.push_back({prev, pts[i]-prev});
        prev = pts[i];
    } 
    
    int area = 0;

    for(auto e: edges){
        area += e.first.imag() * e.second.real();
    }

    if(area<0){
        for(pair<pt, pt>&edge : edges){
            edge = {edge.first+edge.second, -edge.second};
        }
    }

    vector<Interval> inters;
    for(auto e: edges){
        if(e.second.imag()!=0){
            if(e.second.imag()>0){
                inters.push_back(Interval{e.first.real(), e.first.imag(), e.first.imag()+e.second.imag()-1, true});
            }
            else if(e.second.imag()<0){
                inters.push_back(Interval{e.first.real(), e.first.imag()+e.second.imag(), e.first.imag()-1, false});
            }
        }
    }

    auto cmp = [&](Interval& a, Interval& b){
        return a.x<b.x;
    };

    sort(inters.begin(), inters.end(), cmp);
    vector<InterSet> inter_set(2);

    int k = 0;
    Interval prev_inter = Interval{0, 0, 0, true};

    auto chmax = [&](int x){
        if(inter_set[(x+1)%2].intervals.size()==0){
            if(inter_set[0].is_valid && inter_set[1].is_valid){
                k = x;
            }
        }
        else if(inter_set[x%2].intervals.size()==0){
            if(inter_set[0].is_valid && inter_set[1].is_valid){
                k = x-1;
            }
        }
    };
    for(auto e: inters){
        if(e.x!=prev_inter.x){
            //cout<<"nb_unpair: "<<inter_set[0].nb_unpair<<" "<<inter_set[1].nb_unpair<<endl;
            for(int i= 0; i<2; i++){
                inter_set[i].is_valid &= (inter_set[i].nb_unpair ==0);
            }

            chmax(e.x);
        }
        if(inter_set[0].intervals.size()==0 || inter_set[1].intervals.size()==0){
            if(inter_set[0].is_valid && inter_set[1].is_valid){
                k = e.x-1;
            }
        }
        if(e.open){
            inter_set[e.x%2].insert_big(e);
        }
        else{
            inter_set[0].insert_big(e);
            inter_set[1].insert_big(e);
        }

        if(inter_set[0].intervals.size()==0 || inter_set[1].intervals.size()==0){
            if(inter_set[0].is_valid && inter_set[1].is_valid){
                k = e.x;
            }
        }
        prev_inter = e;
    }

    chmax(M);

    cout<<k<<endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 9 / 9
• Subtask 3: 11 / 11
• Subtask 4: 0 / 19
• Subtask 5: 22 / 22
• Subtask 6: 25 / 25
• Subtask 7: 0 / 10