Submission #1135425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135425		Zbyszek99	Building Skyscrapers (CEOI19_skyscrapers)	C++20	8 / 100	1361 ms	194040 KiB

skyscrapers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#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;
};

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

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

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

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}};

vi upd_queue;

set<int> good_points;

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

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;
            }
        }
        else
        {
            forall(it,comp_list[b])
            {
                can_out[it] = 1;
            }
        }
    }
    if(siz(comp_list[comp[a]]) > siz(comp_list[b])) swap(a,b);
    forall(it,queries[a])
    {
        if(comp[it.b] == b)
        {
            upd_queue.pb(it.v);
        }
        else
        {
            queries[b].pb(it);
        }
    } 
    forall(it,comp_list[a])
    {
        comp[it] = b;
        comp_list[b].pb(it);
    }
}

void upd_art(int v, bool first = false)
{
   // cout << v << " v\n";
    int start = -1;
    int ind = 0;
    forall(it,graph8[v])
    {
        if(full[it]) start = ind;
        ind++;
    }
    if(start == -1)
    {
        good_points.insert(v);
        return;
    }
   // cout << "xd\n";
    vi segs;
    int pop = -1;
    int siz_ = 0;
    rep(i,8)
    {
        start++;
        if(start == 8) start = 0;
      //  cout << start << " " << graph8[v][start] << " g\n";
        if(full[graph8[v][start]])
        {
            if(pop != -1)
            {
                if(siz_ > 1 || pop % 2 == 1)
                {
                    segs.pb(graph8[v][pop]);
                }
            }
            pop = -1;
        }
        else
        {
            siz_++;
            pop = start;
        }
    }
   // cout << "xd\n";
    if(pop != -1)
    {
        if(siz_ > 1 || pop % 2 == 1)
        {
            segs.pb(graph8[v][pop]);
        }
    }
    //forall(it,segs) cout << it << " it\n";
    bool is_ok = true;
   // cout << "xd\n";
    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});
            }
        }
    }
    if(is_ok && can_out)
    {
        if(used[v])
        good_points.insert(v);
    }
    else if(good_points.find(v) != good_points.end())
    {
        good_points.erase(good_points.find(v));
    }
}

void make_union(int a, int b)
{
    union_(a,b);
    while(!upd_queue.empty())
    {
        upd_art(upd_queue.back());
        upd_queue.pop_back();
    }
}

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)
        {
            if(point[{points[i].ff+it.ff,points[i].ss+it.ss}] == 0)
            {
                point[{points[i].ff+it.ff,points[i].ss+it.ss}] = cur_point++;
                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(point[{points[i].ff+it.ff,points[i].ss+it.ss}]);
            if(point[{points[i].ff+it.ff,points[i].ss+it.ss}] > n) graph8[point[{points[i].ff+it.ff,points[i].ss+it.ss}]].pb(i);
        }
    }
    rep2(i,1,cur_point-1)
    {
        forall(it,dir4)
        {
            if(point[{points[i].ff+it.ff,points[i].ss+it.ss}] != 0)
            graph4[i].pb(point[{points[i].ff+it.ff,points[i].ss+it.ss}]);
        }
    }
    dfs(1);
    rep2(i,1,n)
    {
        if(!used[i])
        {
            cout << "NO\n";
            return 0;
        }
    }
    rep2(x,0,150002)
    {
        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)
    {
        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--)
    {
        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);
        }
    }
    cout << "YES\n";
    forall(it,ans) cout << it << "\n";
}

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