Submission #1185874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185874		Zbyszek99	Giraffes (JOI22_giraffes)	C++20	100 / 100	5944 ms	5916 KiB

giraffes

#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 rand(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;

const int tree_siz = (1 << 15)-1;
int drzewo[tree_siz];

int get_max(int akt, int p1, int p2, int s1, int s2)
{
    if(p2 < s1 || p1 > s2) return -1e5;
    if(p1 >= s1 && p2 <= s2) return drzewo[akt-1];
    return max(get_max(akt*2,p1,(p1+p2)/2,s1,s2),get_max(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}

void upd(int v)
{
    drzewo[v-1]= max(drzewo[v*2-1],drzewo[v*2]);
    if(v != 1) upd(v/2);
}

void change(int ind, int x, bool is_set = false)
{
    drzewo[tree_siz/2+ind] = max(drzewo[tree_siz/2+ind],x);
    if(is_set) drzewo[tree_siz/2+ind] = x;
    upd((tree_siz/2+ind+1)/2);
}

struct event
{
    int sort_poz, poz, val, ind, type;
    bool operator<(const event& e)
    {
        if(sort_poz != e.sort_poz) return sort_poz < e.sort_poz;
        if(poz != e.poz) return poz < e.poz;
        return type < e.type;
    }
};

pii rotateP(pii point)
{
    return {-point.ss,point.ff};
}

struct square
{
    vector<pii> points;
    square(pii corner, int len)
    {
        points.pb(corner);
        points.pb({corner.ff,corner.ss-len});
        points.pb({corner.ff-len,corner.ss-len});
        points.pb({corner.ff-len,corner.ss});
    }
    void rotate()
    {
        rep(i,4) points[i] = rotateP(points[i]);
        swap(points[0],points[1]);
        swap(points[1],points[2]);
        swap(points[2],points[3]);
    }
};

vector<square> squ;
vector<square> new_squ;
vector<pii> vp;
int min_side[100000];


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    rep(i,tree_siz) drzewo[i] = -1e5;
    int n;
    cin >> n;
    rep2(i,1,n)
    {
        int x;
        cin >> x;
        square new_s({i,x},0);
        new_squ.pb(new_s);
        vp.pb({i,x});
    }
    int ans = n;
    vector<event> events;
    while(!new_squ.empty())
    {
        ans--;
        swap(new_squ,squ);
        new_squ = {};
      //  cout << ans << " iter:\n\nsqu:\n";
     //   forall(it,squ)
     //   {
     //       cout << it.points[0].ff << " " << it.points[0].ss << " " << it.points[0].ss - it.points[1].ss << " squ\n";
      //  }
        rep(ang,4)
        {
            events = {};
            rep(i,siz(squ))
            {
                events.pb({squ[i].points[0].ss - squ[i].points[0].ff,squ[i].points[0].ff+n,squ[i].points[1].ss,i,1});
            }
            rep(i,n)
            {
                min_side[i] = 1e9;
                events.pb({vp[i].ss-vp[i].ff,vp[i].ff+n,-1,i,0});
            }
            sort(all(events));
            forall(it,events)
            {
                if(it.type == 1)
                {
           //      if(ang == 1)   cout << it.poz << " " << it.val << " " << it.ind << " val\n";
                    change(it.poz,it.val);
                }
                else
                {
                    int m = get_max(1,0,tree_siz/2,0,it.poz-1);
          //        if(ang == 1)  cout << it.ind << " " << it.poz << " " << vp[it.ind].ff << " " << vp[it.ind].ss << " " << m << " ans2\n";
                    min_side[it.ind] = min(min_side[it.ind],vp[it.ind].ss - m);
                }
          //      cout << it.ind << " first\n";
            }
            forall(it,events)
            {
                if(it.type == 1)
                change(it.poz,-1e5,1);
            }
            events = {};
            rep(i,siz(squ))
            {
                events.pb({-(squ[i].points[0].ss - squ[i].points[0].ff),squ[i].points[0].ss+n,squ[i].points[2].ff,i,1});
            }
            rep(i,n)
            {
                events.pb({-(vp[i].ss-vp[i].ff),vp[i].ss+n,-1,i,0});
            }
            sort(all(events));
            forall(it,events)
            {
                if(it.type == 1)
                {
                    change(it.poz,it.val);
                }
                else
                {
                    
                    int m = get_max(1,0,tree_siz/2,0,it.poz-1);
                  //  cout << it.ind << " " << m << " ans2\n";
                    min_side[it.ind] = min(min_side[it.ind],vp[it.ind].ff - m);
                }
            //    cout << it.ind << " second\n";
            }
            forall(it,events)
            {
                if(it.type == 1)
                change(it.poz,-1e5,1);
            }
            rep(i,n)
            {
              //  if(ang == 1) cout << min_side[i] << " " << ang << " " << i << " " << vp[i].ff << " " << vp[i].ss << " min_side\n";
                if(min_side[i] <= 10000)
                {
                    square new_s(vp[i],min_side[i]);
                    new_squ.pb(new_s);
                }
            }

            rep(i,n)
            {
                vp[i] = rotateP(vp[i]);
            }
            rep(i,siz(new_squ))
            {
                new_squ[i].rotate();
            }
            rep(i,siz(squ))
            {
                squ[i].rotate();
            }
           // cout << "\nnew angle\n";
        }
     //   cout << " new_squ:\n";
        squ = {};
        forall(it,new_squ)
        {
            
            bool is_ok = true;
            forall(it2,it.points)
            {
                if(it2.ff < 1 || it2.ff > n) is_ok = false;
                if(it2.ss < 1 || it2.ss > n) is_ok = false;
            }
            if(is_ok) 
            {
                squ.pb(it);
             //   cout << it.points[0].ff << " " << it.points[0].ss << " " << it.points[0].ss - it.points[1].ss << " new_squ\n";
            }
        }
        new_squ = squ;
       // if(ans == 7) break;
    }
    cout << ans << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 41 / 41