Submission #724207

#	Time	Username	Problem	Language	Result	Execution time	Memory
724207		n0sk1ll	New Home (APIO18_new_home)	C++14	10 / 100	5072 ms	935836 KiB

new_home

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

const int N=36'000'007;
int tag[N],L[N],R[N];
int idx=0;

vector<vector<pii>> stare;
vector<pii> empt;

int AddPos(int p, int l, int r, int ll, int rr, int x) //positive slope
{
    if (ll>r || rr<l) return 0;
    else if (ll<=l && rr>=r)
    {
        stare.back().pb({p,tag[p]});
        tag[p]=max(tag[p],x);
        return r-l+1;
    }
    else
    {
        int mid=(l+r)/2;
        if (!L[p]) L[p]=++idx;
        if (!R[p]) R[p]=++idx;

        int siz=0;
        siz+=AddPos(L[p],l,mid,ll,rr,x);
        siz+=AddPos(R[p],mid+1,r,ll,rr,x+siz);
        return siz;
    }
}

int AddNeg(int p, int l, int r, int ll, int rr, int x) //negative slope
{
    if (ll>r || rr<l) return 0;
    else if (ll<=l && rr>=r)
    {
        stare.back().pb({p,tag[p]});
        tag[p]=max(tag[p],x);
        return r-l+1;
    }
    else
    {
        int mid=(l+r)/2;
        if (!L[p]) L[p]=++idx;
        if (!R[p]) R[p]=++idx;

        int siz=0;
        siz+=AddNeg(R[p],mid+1,r,ll,rr,x);
        siz+=AddNeg(L[p],l,mid,ll,rr,x+siz);
        return siz;
    }
}

int MaxPos(int p, int l, int r, int s)
{
    if (!p) return -mod;
    int m=tag[p]+s-l;

    int mid=(l+r)/2;
    if (s<=mid) m=max(m,MaxPos(L[p],l,mid,s));
    else m=max(m,MaxPos(R[p],mid+1,r,s));

    return m;
}

int MaxNeg(int p, int l, int r, int s)
{
    if (!p) return -mod;
    int m=tag[p]+r-s;

    int mid=(l+r)/2;
    if (s<=mid) m=max(m,MaxNeg(L[p],l,mid,s));
    else m=max(m,MaxNeg(R[p],mid+1,r,s));

    return m;
}

void rollback()
{
    for (auto [p,v] : stare.back()) tag[p]=v;
    stare.popb();
}

void ispisi(int p, int l, int r)
{
    if (!p) return;
    if (l==r) return;

    int mid=(l+r)/2;
    ispisi(L[p],l,mid),ispisi(R[p],mid+1,r);
}

int ans[300005];

int k=1;
vector<pii> rmv[4444444];
int l[4444444],r[4444444];
vector<pii> qry[4444444]; //lokacija,index

void ToRmv(int p, int ll, int rr, int t, int x)
{
    if (ll>r[p] || rr<l[p]) return;
    if (ll<=l[p] && rr>=r[p]) rmv[p].pb({t,x});
    else ToRmv(2*p,ll,rr,t,x),ToRmv(2*p+1,ll,rr,t,x);
}

multiset<int> gde[300005];

int LOSIH=0;

void dfs(int p)
{
    int kolko=0;
    for (auto [t,x] : rmv[p])
    {
        gde[t].erase(gde[t].find(x));
        auto desni=gde[t].lower_bound(x);
        if (desni!=gde[t].end() && *desni==x) continue;

        if (gde[t].empty()) LOSIH++;
        else if (desni==gde[t].end())
        {
            auto levi=prev(desni);
            stare.pb(empt),AddPos(1,0,1e8,*levi,1e8,0),kolko++;
        }
        else if (desni==gde[t].begin())
        {
            stare.pb(empt),AddNeg(2,0,1e8,0,*desni,0),kolko++;
        }
        else
        {
            auto levi=prev(desni);
            if (*desni==x) levi=desni;

            int a=*levi,b=*desni,pola=(b-a)/2;
            stare.pb(empt),AddPos(1,0,1e8,a,a+pola,0),kolko++;
            stare.pb(empt),AddNeg(2,0,1e8,b-pola,b,0),kolko++;
        }
    }

    if (p<k) dfs(2*p),dfs(2*p+1);
    else
    {
        for (auto [x,ind] : qry[p])
        {
            /*cout<<"("<<ind<<","<<x<<")"<<":"<<endl;
            fff(i,1,2)
            {
                cout<<i<<": ";
                for (auto it : gde[i]) cout<<it<<" ";
                cout<<endl;
            } cout<<endl;*/

            if (LOSIH==0) ans[ind]=max(MaxPos(1,0,1e8,x),MaxNeg(2,0,1e8,x));
            else ans[ind]=-1;
        }
    }

    while (kolko--) rollback();
    for (auto [t,x] : rmv[p])
    {
        if (gde[t].empty()) LOSIH--;
        gde[t].insert(x);
    }
}

int main()
{
    FAST;

    ff(i,0,N) tag[i]=-mod;

    int n,TIPS,q; cin>>n>>TIPS>>q;
    vector<int> kords;

    vector<pair<pii,pii>> segs;

    ff(i,0,n)
    {
        int x,t,a,b;
        cin>>x>>t>>a>>b;
        gde[t].insert(x);

        segs.pb({{0,a-1},{t,x}});
        segs.pb({{b+1,1e8},{t,x}});
        kords.pb(a-1),kords.pb(b+1);
        kords.pb(a),kords.pb(b);
    }

    vector<pii> queries;
    ff(i,0,q)
    {
        int x,y; cin>>x>>y;
        queries.pb({x,y});
        kords.pb(y);
    }

    sort(all(kords));
    kords.erase(unique(all(kords)),kords.end());

    ff(i,0,(int)segs.size())
    {
        segs[i].xx.xx=lower_bound(all(kords),segs[i].xx.xx)-kords.begin();
        segs[i].xx.yy=lower_bound(all(kords),segs[i].xx.yy)-kords.begin();
    }

    ff(i,0,(int)queries.size())
    {
        queries[i].yy=lower_bound(all(kords),queries[i].yy)-kords.begin();
    }



    //Build the DCT segtree

    while (k<(int)kords.size()) k*=2;
    ff(i,0,(int)kords.size()) l[i+k]=kords[i],r[i+k]=kords[i];
    ff(i,(int)kords.size(),k) l[i+k]=mod,r[i+k]=mod;
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];

    ff(i,0,(int)queries.size()) qry[queries[i].yy+k].pb({queries[i].xx,i});

    for (auto it : segs) ToRmv(1,it.xx.xx,it.xx.yy,it.yy.xx,it.yy.yy);



    //Zavrsetak zadatka

    idx=2;

    fff(tip,1,TIPS) if (!gde[tip].empty())
    {
        vector<int> temp;
        for (auto it : gde[tip]) temp.pb(it);

        stare.pb(empt),AddNeg(2,0,1e8,0,temp[0],0);
        ff(i,1,(int)temp.size())
        {
            int pola=(temp[i]-temp[i-1])/2;
            stare.pb(empt),AddPos(1,0,1e8,temp[i-1],temp[i-1]+pola,0);
            stare.pb(empt),AddNeg(2,0,1e8,temp[i]-pola,temp[i],0);
        }
        stare.pb(empt),AddPos(1,0,1e8,temp.back(),1e8,0);
    }

    dfs(1);
    ff(i,0,q) cout<<ans[i]<<"\n";
}

//Note to self: Check for overflow

/*

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1

*/

Compilation message (stderr)

new_home.cpp: In function 'void rollback()':
new_home.cpp:114:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |     for (auto [p,v] : stare.back()) tag[p]=v;
      |               ^
new_home.cpp: In function 'void dfs(int)':
new_home.cpp:148:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |     for (auto [t,x] : rmv[p])
      |               ^
new_home.cpp:178:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  178 |         for (auto [x,ind] : qry[p])
      |                   ^
new_home.cpp:194:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  194 |     for (auto [t,x] : rmv[p])
      |               ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20