Submission #200673

#	Time	Username	Problem	Language	Result	Execution time	Memory
200673		gs18115	New Home (APIO18_new_home)	C++14	100 / 100	4590 ms	273424 KiB

new_home

#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+8;
const ll INF=1e18;
const int siz=1010101;
struct seg
{
    int t[2020202];
    seg()
    {
        fill(t,t+2020202,-inf);
    }
    void si(int n,int s,int e,int x,int p)
    {
        if(s==e)
        {
            t[n]=p;
            return;
        }
        int m=s+e>>1;
        if(x>m)
            si(n*2+1,m+1,e,x,p);
        else
            si(n*2,s,m,x,p);
        t[n]=max(t[n*2],t[n*2+1]);
        return;
    }
    int sq(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return -inf;
        if(S<=s&&e<=E)
            return t[n];
        int m=s+e>>1;
        return max(sq(n*2,s,m,S,E),sq(n*2+1,m+1,e,S,E));
    }
}st1,st2;
priority_queue<int>pq1[siz],pq2[siz];
priority_queue<int>dl1[siz],dl2[siz];
inline int get(priority_queue<int>&x,priority_queue<int>&y)
{
    while(!y.empty()&&x.top()==y.top())
        x.pop(),y.pop();
    return x.empty()?-inf:x.top();
}
vector<int>cp;
inline void add1(int x0,int x)
{
    if(x0==-inf)
        return;
    int ci=upper_bound(all(cp),x)-cp.begin()-1;
    pq1[ci].ep(-x0);
    st1.si(1,0,cp.size()-1,ci,get(pq1[ci],dl1[ci]));
    return;
}
inline void add2(int x0,int x)
{
    if(x0==inf)
        return;
    int ci=lower_bound(all(cp),x)-cp.begin();
    pq2[ci].ep(x0);
    st2.si(1,0,cp.size()-1,ci,get(pq2[ci],dl2[ci]));
    return;
}
inline void del1(int x0,int x)
{
    if(x0==-inf)
        return;
    int ci=upper_bound(all(cp),x)-cp.begin()-1;
    dl1[ci].ep(-x0);
    st1.si(1,0,cp.size()-1,ci,get(pq1[ci],dl1[ci]));
    return;
}
inline void del2(int x0,int x)
{
    if(x0==inf)
        return;
    int ci=lower_bound(all(cp),x)-cp.begin();
    dl2[ci].ep(x0);
    st2.si(1,0,cp.size()-1,ci,get(pq2[ci],dl2[ci]));
    return;
}
multiset<int>pts[siz];
inline void add(int tp,int x)
{
    auto it=pts[tp].lower_bound(x);
    int nxt=*it;
    if(nxt==x)
    {
        pts[tp].ep(x);
        return;
    }
    int prv=*--it;
    del1(prv,prv+nxt>>1);
    del2(nxt,prv+nxt>>1);
    add1(prv,prv+x>>1);
    add2(x,prv+x>>1);
    add1(x,x+nxt>>1);
    add2(nxt,x+nxt>>1);
    pts[tp].ep(x);
    return;
}
inline void del(int tp,int x)
{
    pts[tp].erase(pts[tp].find(x));
    auto it=pts[tp].lower_bound(x);
    int nxt=*it;
    if(nxt==x)
        return;
    int prv=*--it;
    del1(prv,prv+x>>1);
    del2(x,prv+x>>1);
    del1(x,x+nxt>>1);
    del2(nxt,x+nxt>>1);
    add1(prv,prv+nxt>>1);
    add2(nxt,prv+nxt>>1);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k,q;
    cin>>n>>k>>q;
    vector<pair<int,pi> >va,vb;
    for(int i=0;i<n;i++)
    {
        int x,t,a,b;
        cin>>x>>t>>a>>b;
        va.eb(a-1,pi(x*2,t-1));
        vb.eb(b,pi(x*2,t-1));
    }
    vector<pair<int,pi> >qv;
    for(int i=0;i<q;i++)
    {
        int x,y;
        cin>>x>>y;
        qv.eb(y,pi(x*2,i));
        cp.eb(x*2);
    }
    cp.eb(-inf);
    cp.eb(inf);
    sort(all(cp));
    cp.erase(unique(all(cp)),cp.end());
    for(int i=0;i<k;i++)
    {
        pts[i].ep(-inf);
        pts[i].ep(inf);
    }
    sort(all(va));
    sort(all(vb));
    sort(all(qv));
    vector<int>ans(q,0);
    int c=0;
    int ai=0;
    int bi=0;
    vector<int>ct(k,0);
    for(auto&t:qv)
    {
        while(ai<va.size()&&va[ai].fi<t.fi)
        {
            add(va[ai].se.se,va[ai].se.fi);
            if(ct[va[ai].se.se]++==0)
                c++;
            ai++;
        }
        while(bi<vb.size()&&vb[bi].fi<t.fi)
        {
            del(vb[bi].se.se,vb[bi].se.fi);
            if(--ct[vb[bi].se.se]==0)
                c--;
            bi++;
        }
        if(c<k)
        {
            ans[t.se.se]=-2;
            continue;
        }
        int x=lower_bound(all(cp),t.se.fi)-cp.begin();
        int m1=st1.sq(1,0,cp.size()-1,x,cp.size()-1);
        int m2=st2.sq(1,0,cp.size()-1,0,x);
        ans[t.se.se]=max(t.se.fi+m1,m2-t.se.fi);
    }
    for(int i=0;i<q;i++)
        cout<<ans[i]/2<<'\n';
    cout.flush();
    return 0;
}

Compilation message (stderr)

new_home.cpp: In member function 'void seg::si(int, int, int, int, int)':
new_home.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m=s+e>>1;
               ~^~
new_home.cpp: In member function 'int seg::sq(int, int, int, int, int)':
new_home.cpp:48:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m=s+e>>1;
               ~^~
new_home.cpp: In function 'void add(int, int)':
new_home.cpp:108:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     del1(prv,prv+nxt>>1);
              ~~~^~~~
new_home.cpp:109:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     del2(nxt,prv+nxt>>1);
              ~~~^~~~
new_home.cpp:110:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     add1(prv,prv+x>>1);
              ~~~^~
new_home.cpp:111:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     add2(x,prv+x>>1);
            ~~~^~
new_home.cpp:112:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     add1(x,x+nxt>>1);
            ~^~~~
new_home.cpp:113:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     add2(nxt,x+nxt>>1);
              ~^~~~
new_home.cpp: In function 'void del(int, int)':
new_home.cpp:125:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     del1(prv,prv+x>>1);
              ~~~^~
new_home.cpp:126:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     del2(x,prv+x>>1);
            ~~~^~
new_home.cpp:127:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     del1(x,x+nxt>>1);
            ~^~~~
new_home.cpp:128:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     del2(nxt,x+nxt>>1);
              ~^~~~
new_home.cpp:129:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     add1(prv,prv+nxt>>1);
              ~~~^~~~
new_home.cpp:130:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     add2(nxt,prv+nxt>>1);
              ~~~^~~~
new_home.cpp: In function 'int main()':
new_home.cpp:174:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ai<va.size()&&va[ai].fi<t.fi)
               ~~^~~~~~~~~~
new_home.cpp:181:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(bi<vb.size()&&vb[bi].fi<t.fi)
               ~~^~~~~~~~~~

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