Submission #1135677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135677		Zbyszek99	Building Skyscrapers (CEOI19_skyscrapers)	C++20	100 / 100	3027 ms	420748 KiB

skyscrapers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma inline
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct query
{
    int v,a,b;
};

const int maxn = 1350001;

vi graph8[maxn];
vi graph4[maxn];
map<pii,int> point;
pii poz[maxn];
bool used[maxn];
bool can_out[maxn];
bool can_out2[maxn];
bool odw[maxn];
bool full[maxn];

int comp[maxn];
vi comp_list[maxn];
vector<query> queries[maxn];

int max_on_x[maxn];
int max_on_y[maxn];
int min_on_x[maxn];
int min_on_y[maxn];

vector<pii> dir8 = {{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1}};
vector<pii> dir4 = {{0,1},{0,-1},{1,0},{-1,0}};

unordered_set<int> upd_queue;

set<int> good_points;

inline void dfs(int v)
{
    used[v] = true;
    forall(it,graph8[v])
    {
        if(!used[it] && full[it])
        {
            dfs(it);
        }
    }
}

inline void union_(int a, int b)
{
    if(comp[a] == comp[b]) return;
    a = comp[a];
    b = comp[b];
    if(can_out[a] != can_out[b])
    {
        if(can_out[a])
        {
            forall(it,comp_list[b])
            {
                can_out[it] = 1;
                forall(it2,graph4[it])
                {
                    if(full[it2] && !can_out2[it2])
                    upd_queue.insert(it2);
                }
            }
        }
        else
        {
            forall(it,comp_list[a])
            {
                can_out[it] = 1;
                forall(it2,graph4[it])
                {
                    if(full[it2] && !can_out2[it2])
                    upd_queue.insert(it2);
                }
            }
        }
    }
    if(siz(comp_list[comp[a]]) + siz(queries[a]) > siz(comp_list[b]) + siz(queries[b])) swap(a,b);
    forall(it,queries[a])
    {
        //cout << it.v << " " << it.a << " " << it.b << " " << b << " " << comp[it.b] << " query\n";
        if(comp[it.b] == b)
        {
            upd_queue.insert(it.v);
        }
        else if(comp[it.b] != a)
        {
            queries[b].pb(it);
        }
    } 
    forall(it,comp_list[a])
    {
        comp[it] = b;
        comp_list[b].pb(it);
    }
}

vi segs;

inline void upd_art(int v, bool first = false)
{
    if(!full[v]) return;
    // cout << "\n" <<  v << " v\n";
    int start = -1;
    int ind = 0;
    forall(it,graph8[v])
    {
        if(full[it]) 
        {
            start = ind;
            break;
        }
        ind++;
    }
    if(start == -1)
    {
        good_points.insert(v);
        return;
    }
   // cout << "xd\n";
    segs = {};
    int pop = 100;
    int siz_ = 0;
    rep(i,8)
    {
        start++;
        if(start == 8) start = 0;
        if(full[graph8[v][start]])
        {
            if(siz_ > 1 || (pop & 1))
            {
                segs.pb(graph8[v][pop]);
            }
            siz_ = 0;
            pop = 100;
        }
        else
        {
            siz_++;
            pop = start;
        }
    }
   // cout << "xd\n";
    if(siz_ > 1 || (pop & 1))
    {
     //   cout << pop << " add\n";
        segs.pb(graph8[v][pop]);
    }
    //forall(it,segs) cout << it << " it\n";
    bool is_ok = true;
    bool cu = false;
    if(!can_out2[v])
    {
        forall(it,graph4[v])
        {
            if(can_out[it]) cu = true;
        }
        if(cu) can_out2[v] = 1;
    }
    forall(it1,segs)
    {
        forall(it2,segs)
        {
            if(it1 == it2) continue;
        //    cout << comp[it1] << " " << comp[it2] << " " << it1 << " " << it2 << " it\n";
            if(comp[it1] == comp[it2])
            {
                is_ok = false;
            }
            else if(first)
            {
                queries[comp[it1]].pb({v,it1,it2});
            }
        }
    }
  //  cout << is_ok << " " << can_out2[v] << " can\n";
    if(is_ok && can_out2[v])
    {
        good_points.insert(v);
    }
    else if(good_points.find(v) != good_points.end())
    {
        good_points.erase(good_points.find(v));
    }
}

inline void make_union(int a, int b)
{
    union_(a,b);
    forall(it,upd_queue)
    {
        upd_art(it);
    }
    upd_queue = {};
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,t;
    cin >> n >> t;
    vi ans(n);
    vector<pii> points = {{0,0}};
    int min_x = 1e9+1;
    int min_y = 1e9+1; 
    rep2(i,1,n)
    {
        int x,y;
        cin >> x >> y;
        min_x = min(min_x,x);
        min_y = min(min_y,y);
        points.pb({x,y});
    }
    rep2(i,1,n)
    {
        points[i].ff -= min_x - 1;
        points[i].ss -= min_y - 1;
        point[points[i]] = i;
        poz[i] = points[i];
        full[i] = 1;
    }
    int cur_point = n+1;
    rep2(i,1,n)
    {
        forall(it,dir8)
        {
            int p = point[{points[i].ff+it.ff,points[i].ss+it.ss}];
            if(p == 0)
            {
                point[{points[i].ff+it.ff,points[i].ss+it.ss}] = cur_point++;
                p = cur_point-1;
                points.pb({points[i].ff+it.ff,points[i].ss+it.ss});
            }
         //   cout << i << " " << point[{points[i].ff+it.ff,points[i].ss+it.ss}] << " i\n";
            graph8[i].pb(p);
            if(p > n) graph8[p].pb(i);
        }
    }
    rep2(i,1,cur_point-1)
    {
        forall(it,dir4)
        {
            int p = point[{points[i].ff+it.ff,points[i].ss+it.ss}];
            if(p != 0)
            graph4[i].pb(p);
        }
    }
    dfs(1);
    rep2(i,1,n)
    {
        if(!used[i])
        {
            cout << "NO\n";
            return 0;
        }
    }
    rep2(x,0,maxn-1)
    {
        max_on_x[x] = -1e9;
        max_on_y[x] = -1e9;
        min_on_x[x] = 1e9;
        min_on_y[x] = 1e9;
    }
    rep2(i,1,cur_point-1)
    {
        comp[i] = i;
        comp_list[i] = {i};
        max_on_x[points[i].ff] = max(points[i].ss,max_on_x[points[i].ff]);
        min_on_x[points[i].ff] = min(points[i].ss,min_on_x[points[i].ff]);
        max_on_y[points[i].ss] = max(points[i].ff,max_on_y[points[i].ss]);
        min_on_y[points[i].ss] = min(points[i].ff,min_on_y[points[i].ss]);
    }
    rep2(i,1,cur_point-1)
    {
        if(points[i].ff == max_on_y[points[i].ss] || points[i].ff == min_on_y[points[i].ss])
        {
            can_out[i] = 1;
        }
        if(points[i].ss == max_on_x[points[i].ff] || points[i].ss == min_on_x[points[i].ff])
        {
            can_out[i] = 1;
        }
    }
    rep2(i,1,cur_point-1)
    {
      //  cout << i << " " << can_out[i] << " can_out\n";
        if(full[i]) continue;
        forall(it,graph4[i])
        {
            if(!full[it]) 
            {
                //cout << it << " " << i << " union\n";
                make_union(it,i);
            }
        }
    }
    rep2(i,1,n)
    {
      //  cout << i << " upd\n";
        upd_art(i,1);
        //forall(it,good_points) cout << it << " good\n";
    }
    for(int i = n-1; i >= 0; i--)
    {
      //  cout << "xd\n";
        auto g = good_points.end();
        g--;
        int best = *g;
      //  cout << best << " best\n";
        ans[i] = best;
        good_points.erase(good_points.find(best));
        used[best] = 0;
        full[best] = 0;
        forall(it,graph4[best])
        {
            if(!full[it]) make_union(best,it);
        }
        forall(it,graph8[best])
        {
            if(full[it]) upd_art(it,1);
        }
    }
    cout << "YES\n";
    forall(it,ans) cout << it << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 12 / 12
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 10 / 10
• Subtask 7: 19 / 19