Submission #724212

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
724212	2023-04-14T21:52:18 Z	n0sk1ll	New Home (APIO18_new_home)	C++14	10 / 100	5000 ms	890408 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++;
            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 (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

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

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	332748 KB	Output is correct
2	Correct	158 ms	332676 KB	Output is correct
3	Incorrect	143 ms	332748 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	150 ms	332748 KB	Output is correct
2	Correct	158 ms	332676 KB	Output is correct
3	Incorrect	143 ms	332748 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	3226 ms	745764 KB	Output is correct
2	Correct	3572 ms	747168 KB	Output is correct
3	Correct	1717 ms	579164 KB	Output is correct
4	Correct	3160 ms	706692 KB	Output is correct
5	Correct	3369 ms	704316 KB	Output is correct
6	Correct	3453 ms	735600 KB	Output is correct
7	Correct	1638 ms	579316 KB	Output is correct
8	Correct	2731 ms	700652 KB	Output is correct
9	Correct	3499 ms	801920 KB	Output is correct
10	Correct	3684 ms	819436 KB	Output is correct
11	Correct	2016 ms	746068 KB	Output is correct
12	Correct	2581 ms	794156 KB	Output is correct