Submission #1079285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079285		anton	Tiles (BOI24_tiles)	C++17	0 / 100	1004 ms	18744 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;
    }
};

struct InterSet{
    set<Interval> intervals;
    bool is_valid = true;
    int last_valid = 1e18;
    void insert(Interval new_inter){
        auto lb = intervals.upper_bound(new_inter);
        if(lb!=intervals.begin()){
            --lb;
        }
        auto rb = intervals.upper_bound(Interval{0, new_inter.yr, false});
        if(rb!= intervals.end()){
            ++rb;
        }
            
        for(auto it = intervals.begin(); it!= rb;){
            Interval val = *it;
            it = intervals.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})){
                        if(is_valid && (new_inter.x-val.x)%2==1){
                            last_valid = new_inter.x-1;
                            //cout<<"breaking is "<<new_inter.yl<<" "<<new_inter.yr<<endl;
                        }
                        is_valid &= (new_inter.x-val.x)%2==0;
                    }
                }
                
                if(val2.is_valid()){
                    intervals.insert(val2);
                }
            }
        }
        if(new_inter.open){
            intervals.insert(new_inter);
        }

        for(auto e: intervals){
            //cout<<e.yl<<" "<<e.yr<<" ";
        }
        //cout<<endl;
    }
};
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){
            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);


    InterSet inter_set;

    int k = 0;

    for(auto e: inters){
        inter_set.insert(e);
    }

    cout<<min(M, inter_set.last_valid)<<endl;
}

Compilation message (stderr)

Main.cpp: In member function 'void InterSet::insert(Interval)':
Main.cpp:84:18: warning: variable 'e' set but not used [-Wunused-but-set-variable]
   84 |         for(auto e: intervals){
      |                  ^
Main.cpp: In function 'int main()':
Main.cpp:138:9: warning: unused variable 'k' [-Wunused-variable]
  138 |     int k = 0;
      |         ^

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