Submission #724216

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
724216	2023-04-14T22:03:32 Z	n0sk1ll	New Home (APIO18_new_home)	C++17	10 / 100	5000 ms	883048 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-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);
    }

    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

*/

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	332876 KB	Output is correct
2	Correct	154 ms	332720 KB	Output is correct
3	Incorrect	145 ms	332756 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	332876 KB	Output is correct
2	Correct	154 ms	332720 KB	Output is correct
3	Incorrect	145 ms	332756 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2479 ms	658256 KB	Output is correct
2	Correct	3488 ms	734624 KB	Output is correct
3	Correct	1667 ms	566124 KB	Output is correct
4	Correct	2246 ms	643888 KB	Output is correct
5	Correct	3036 ms	692132 KB	Output is correct
6	Correct	3244 ms	723536 KB	Output is correct
7	Correct	1505 ms	565552 KB	Output is correct
8	Correct	2005 ms	643476 KB	Output is correct
9	Correct	2193 ms	667600 KB	Output is correct
10	Correct	2097 ms	631740 KB	Output is correct
11	Correct	1914 ms	732224 KB	Output is correct
12	Correct	2413 ms	776508 KB	Output is correct