Submission #724219

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
724219	2023-04-14T22:17:14 Z	n0sk1ll	New Home (APIO18_new_home)	C++14	10 / 100	5000 ms	766432 KB

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=28'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));
        if (gde[t].empty()) LOSIH++;
        if (LOSIH) continue;

        auto desni=gde[t].lower_bound(x);
        if (desni!=gde[t].end() && *desni==x) continue;

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

            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 (LOSIH);
    else 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},{t,x}});
        segs.pb({{b,1e8},{t,x}});
        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)
    {
        if (it.xx.xx==0) ToRmv(1,it.xx.xx,it.xx.yy-1,it.yy.xx,it.yy.yy);
        else ToRmv(1,it.xx.xx+1,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);
    }

    ff(i,0,q) ans[i]=-1;
    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

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:180:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  180 |         for (auto [x,ind] : qry[p])
      |                   ^
new_home.cpp:196:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  196 |     for (auto [t,x] : rmv[p])
      |               ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	332748 KB	Output is correct
2	Incorrect	146 ms	332712 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	142 ms	332748 KB	Output is correct
2	Incorrect	146 ms	332712 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2184 ms	653304 KB	Output is correct
2	Correct	1654 ms	594380 KB	Output is correct
3	Correct	1546 ms	560708 KB	Output is correct
4	Correct	2037 ms	638756 KB	Output is correct
5	Correct	1697 ms	572868 KB	Output is correct
6	Correct	1623 ms	588612 KB	Output is correct
7	Correct	1399 ms	560900 KB	Output is correct
8	Correct	1953 ms	638780 KB	Output is correct
9	Correct	2127 ms	662968 KB	Output is correct
10	Correct	2023 ms	626560 KB	Output is correct
11	Correct	1266 ms	594380 KB	Output is correct
12	Correct	1605 ms	619684 KB	Output is correct