Submission #724207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
724207	2023-04-14T21:31:44 Z	n0sk1ll	New Home (APIO18_new_home)	C++14	10 / 100	5000 ms	935836 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=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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	364140 KB	Output is correct
2	Correct	182 ms	364044 KB	Output is correct
3	Incorrect	166 ms	364072 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	174 ms	364140 KB	Output is correct
2	Correct	182 ms	364044 KB	Output is correct
3	Incorrect	166 ms	364072 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	3285 ms	786316 KB	Output is correct
2	Correct	3458 ms	778836 KB	Output is correct
3	Correct	1676 ms	610676 KB	Output is correct
4	Correct	2814 ms	738204 KB	Output is correct
5	Correct	3166 ms	735640 KB	Output is correct
6	Correct	3365 ms	767052 KB	Output is correct
7	Correct	1525 ms	610712 KB	Output is correct
8	Correct	2422 ms	732172 KB	Output is correct
9	Correct	3004 ms	833284 KB	Output is correct
10	Correct	3399 ms	850848 KB	Output is correct
11	Correct	2033 ms	777332 KB	Output is correct
12	Correct	2496 ms	825792 KB	Output is correct