Submission #1157683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157683		vicvic	Towers (NOI22_towers)	C++20	100 / 100	429 ms	123524 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int NMAX=1e6;
int n;
int x[NMAX+5], y[NMAX+5], indx[NMAX+5], indy[NMAX+5];
vector <int> xs[NMAX+5], ys[NMAX+5];
int top[NMAX+5], bottom[NMAX+5], min_line[NMAX+5], max_line[NMAX+5];
vector <int> try_again;
void add_point (int ind, bool type)
{
    if (type)
        top[ind]=1;
    else bottom[ind]=1;
    int &mn=min_line[y[ind]];
    int &mx=max_line[y[ind]];
    if (mn==-1)
    {
        mn=mx=ind;
    }
    else
    {
        if (x[mn]>x[ind])
        {
            if (mx!=mn) try_again.push_back (mn);
            mn=ind;
        }
        if (x[mx]<x[ind])
        {
            if (mx!=mn) try_again.push_back (mx);
            mx=ind;
        }
    }
    if (mx!=ind && mn!=ind)
    {
        try_again.push_back (ind);
    }
}
int main ()
{
    ios :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> x[i] >> y[i];
        xs[x[i]].push_back (i);
        ys[y[i]].push_back (i);
    }
    for (int i=1;i<=NMAX;i++)
    {
        min_line[i]=max_line[i]=-1;
        sort (xs[i].begin(), xs[i].end(), [&] (int a, int b) {return y[a]<y[b];});
        sort (ys[i].begin(), ys[i].end(), [&] (int a, int b) {return x[a]<x[b];});
        for (int j=0;j<xs[i].size();j++)
        {
            indx[xs[i][j]]=j;
        }
        for (int j=0;j<ys[i].size();j++)
        {
            indy[ys[i][j]]=j;
        }
    }
    for (int i=1;i<=NMAX;i++)
    {
        if (xs[i].empty())
            continue;
        add_point (xs[i][0], 0);
        add_point (xs[i][xs[i].size()-1], 1);
    }
    for (int it=0;it<try_again.size();it++)
    {
        int ind=try_again[it];
        if (top[ind] && bottom[ind])
        {
            bottom[ind]=top[ind]=0;
            continue;
        }
        if (top[ind])
        {
            top[ind]=0;
            add_point (xs[x[ind]][indx[ind]-1], 1);
        }
        if (bottom[ind])
        {
            bottom[ind]=0;
            add_point (xs[x[ind]][indx[ind]+1], 0);
        }
    }
    for (int i=1;i<=n;i++)
    {
        cout << (bottom[i] || top[i]);
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 31 / 31
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19