Submission #1080774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080774		abouton	Tiles (BOI24_tiles)	C++17	71 / 100	79 ms	12736 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct ar
{
    int yD, yF, x;
    bool typ;
    bool operator<(const ar &autre) const
    {
        if (x == autre.x) return yD < autre.yD;
        return x < autre.x;
    }
};

struct inter
{
    int y1, y2;
    bool par;
    bool operator<(const inter &autre) const
    {
        return y1 < autre.y1;
    }
};
int nbI;
vector<ar> aretes;
set<inter> cur;
int N, M, maxi;
int nbA;
int nb[2];

void aj(int y1, int y2, int x)
{
    auto it = cur.lower_bound({y2,0,0});
    assert (it != cur.begin());
    assert(it != cur.end());
    auto prec = *prev(it);
    auto suiv = *it;
    if (y1 == prec.y2 && (x%2) == prec.par)
    {
        y1 = prec.y1;
        nb[prec.par]--;
        nbI -= ((prec.y1+prec.y2)%2);
        cur.erase(prec);
        if ((prec.par+x)%2) nb[(x+1)%2]++;
    }
    if (y2==suiv.y1 && (x%2) == suiv.par)
    {
        y2 = suiv.y2;
        nb[suiv.par]--;
        nbI -= ((suiv.y1+suiv.y2)%2);
        cur.erase(suiv);
        if ((suiv.par+x)%2) nb[(x+1)%2]++;
    }
    nb[(bool)(x%2)]++;
    cur.insert({y1,y2,(bool)(x%2)});
    nbI += ((y1+y2)%2);
}

void ret(int y1,int y2, int x)
{
    auto it = cur.upper_bound({y1,0,0});
    auto mec = *prev(it);
    //cout << y1 << ' ' << y2 << ' ' << mec.y1 << ' ' << mec.y2 << '\n';
    //cout << (*it).y1 << ' ' << (*it).y2 << '\n';
    //assert (mec.y1 <= y1 && mec.y2 >= y2);
    //cout << "alors " << y1 << ' ' << y2 << ' ' << mec.y1 << ' ' << mec.y2 << '\n';
    if (mec.y2 < y2)
    {
        nb[(x+1)%2] ++;
        cout << maxi;
        exit(0);
    }
    if ((mec.par+x)%2) nb[(x+1)%2] ++;
    nb[mec.par]--;
    nbI -= ((mec.y1+mec.y2)%2);
    cur.erase(mec);

    if (y1 > mec.y1)
    {

        nbI += ((mec.y1+y1)%2);
        //cout << mec.y1 << ' ' <<y1<<'\n';
        cur.insert({mec.y1, y1, (bool)(x%2)});
        //cout << 'a';
        //for (auto i : cur) cout << i.y1 <<i.y2<<' ';
        nb[(bool)(x%2)]++;
    }
    if (y2 < mec.y2)
    {        
        nbI += ((mec.y2+y2)%2);
        cur.insert({y2, mec.y2, (bool)(x%2)});
        nb[(bool)(x%2)]++;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin >> N >> M;
    maxi = 0;
    bool sens = 0;
    int precX, precY, x0, y0;
    cin >> precX >> precY;
    x0 = precX; y0 = precY;
    for (int i = 0; i < N; i ++)
    {
        int x, y;
        if (i<N-1) cin >> x >> y;
        else
        {
            x = x0; y = y0;
        }
        if (x == precX)
        {
            aretes.push_back({precY, y, x, 0});
        }
        if (x == 0 && precX == 0) {sens = !(y>precY);}
        precX = x; precY = y;
    }
    nbA = aretes.size();
    for (int i = 0; i < nbA; i ++)
    {
        aretes[i].typ = sens ^ (aretes[i].yF > aretes[i].yD);
        //cout << (int) sens << (int)(aretes[i].yF>aretes[i].yD);
        if (aretes[i].yF < aretes[i].yD) swap(aretes[i].yD, aretes[i].yF);
    }

    //for (auto i : aretes)
    //{
    //    cout << i.yD << ' ' << i.yF << ' ' << i.x << ' ' << (int)i.typ << '\n';
    //}

    sort(aretes.begin(), aretes.end());
    cur.insert({-1, -1,0});
    cur.insert({1000000001, 1000000001, 0});
    for (int i = 0; i < nbA; i ++)
    {
        if (nb[(aretes[i].x+1)%2]==0)
            maxi = aretes[i].x;
        else if (nb[(aretes[i].x)%2]==0)
            maxi = aretes[i].x-1;
            
        if (aretes[i].typ) aj(aretes[i].yD, aretes[i].yF, aretes[i].x);
        else ret(aretes[i].yD, aretes[i].yF, aretes[i].x);

        /*cout << "nouv : " << aretes[i].yD << ' ' << aretes[i].yF << ' ' << aretes[i].x << '\n';
        for (auto truc : cur)
        {
            cout << truc.y1 << ' ' << truc.y2 << " et " << nbI << '\n';
        }
        cout << '\n';*/

        if (i == nbA-1 || aretes[i+1].x > aretes[i].x)
        {
            //cout << nb[0] << ' ' << nb[1] << '\n';
            if (nbI!=0)
            {
                cout << maxi <<'\n';
                return 0;
            }
        }
    }
    cout << maxi << '\n';
}

• 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