제출 #159425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159425		arnold518	새 집 (APIO18_new_home)	C++14	0 / 100	5101 ms	378372 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;
const int MAXVAL = 1e8;

struct Query
{
    int t, x, k, p;
    bool operator < (const Query &p)
    {
        if(t!=p.t) return t<p.t;
        return k>p.k;
    }
};

int N, K, Q, ans[MAXN+10], SZ, chk;
vector<Query> query;
multiset<int> S[MAXN+10];
set<int> scomp;
vector<int> comp;

int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin(); }

priority_queue<int, vector<int>, less<int>> tree1[4*MAXN+10];
priority_queue<int, vector<int>, less<int>> dead1[4*MAXN+10];

priority_queue<int, vector<int>, greater<int>> tree2[4*MAXN+10];
priority_queue<int, vector<int>, greater<int>> dead2[4*MAXN+10];

ll query1(int x)
{
    int y=x;
    x=getcomp(x);
    int ret=0;
    for(; x>0; x-=(x&-x))
    {
        while(!tree1[x].empty() && !dead1[x].empty() && tree1[x].top()==dead1[x].top()) tree1[x].pop(), dead1[x].pop();
        if(!tree1[x].empty())
        {
            //printf("QUERY1 %d %d\n", x, tree1[x].top()-y);
            ret=max(ret, tree1[x].top()-y);
        }
    }
    return ret;
}

void erase1(int x, int y)
{
    //printf("ERASE1 %d %d\n", x, y);
    x=getcomp(x);
    for(; x<=SZ; x+=(x&-x))
    {
        dead1[x].push(y);
    }
}

void insert1(int x, int y)
{
    //printf("INSERT1 %d %d\n", x, y);
    x=getcomp(x);
    for(; x<=SZ; x+=(x&-x))
    {
        tree1[x].push(y);
    }
}

ll query2(int x)
{
    int y=x;
    x=getcomp(x);
    x=SZ-x+1;
    int ret=0;
    for(; x>0; x-=(x&-x))
    {
        while(!tree2[x].empty() && !dead2[x].empty() && tree2[x].top()==dead2[x].top()) tree2[x].pop(), dead2[x].pop();
        if(!tree2[x].empty())
        {
            //printf("QUERY1 %d %d\n", x, y-tree2[x].top());
            ret=max(ret, y-tree2[x].top());
        }
    }
    return ret;
}

void erase2(int x, int y)
{
    swap(x, y);
    //printf("ERASE2 %d %d\n", x, y);
    x=getcomp(x);
    x=SZ-x+1;
    for(; x<=SZ; x+=(x&-x))
    {
        dead2[x].push(y);
    }
}

void insert2(int x, int y)
{
    swap(x, y);
    //printf("INSERT2 %d %d\n", x, y);
    x=getcomp(x);
    x=SZ-x+1;
    for(; x<=SZ; x+=(x&-x))
    {
        tree2[x].push(y);
    }
}

int main()
{
    int i, j;

    scanf("%d%d%d", &N, &K, &Q);
    for(i=1; i<=N; i++)
    {
        int x, t, a, b;
        scanf("%d%d%d%d", &x, &t, &a, &b); b++; x*=2;
        query.push_back({a, x, t, 1});
        query.push_back({b, x, t, -1});
        scomp.insert(x);
    }
    for(i=1; i<=Q; i++)
    {
        int l, x;
        scanf("%d%d", &x, &l); x*=2;
        query.push_back({l, x, -i, 0});
        scomp.insert(x);
    }
    sort(query.begin(), query.end());

    for(i=1; i<=N; i++) S[i].insert(0), S[i].insert(2e8);
    scomp.insert(0); scomp.insert(2e8);
    for(auto now : query)
    {
        if(now.p==1)
        {
            if(S[now.k].find(now.x)!=S[now.k].end())
            {
                auto it=S[now.k].lower_bound(now.x);
                int r=*it, l=*(--it);
                scomp.insert(l+now.x>>1);
                scomp.insert(r+now.x>>1);
            }
            S[now.k].insert(now.x);
        }
        else if(now.p==-1) S[now.k].erase(S[now.k].find(now.x));
    }

    comp.push_back(-1);
    for(auto it : scomp) comp.push_back(it);
    SZ=comp.size();

    for(i=1; i<=N; i++) S[i].clear();

    for(auto now : query)
    {
        //printf("===============\n");
        int x=now.x;
        if(now.p==0)
        {
            if(chk!=K) ans[-now.k]=-1;
            else ans[-now.k]=max(query1(x), query2(x))>>1;
            //printf("!%d %d %d\n", -now.k, query1(x), query2(x));
        }
        else if(now.p==1)
        {
            if(S[now.k].find(now.x)==S[now.k].end())
            {
                if(S[now.k].size()==0)
                {
                    insert1(0, x);
                    insert2(x, 2e8);
                    chk++;
                }
                else if(S[now.k].size()==1)
                {
                    int l=*S[now.k].begin();
                    if(l<x)
                    {
                        erase2(l, 2e8);
                        insert2(l, l+x>>1);
                        insert1(l+x>>1, x);
                        insert2(x, 2e8);
                    }
                    else
                    {
                        erase1(0, l);
                        insert1(0, x);
                        insert2(x, l+x>>1);
                        insert1(l+x>>1, l);
                    }
                }
                else
                {
                    auto it=S[now.k].lower_bound(x);
                    int r=*it, l=*(--it);
                    erase2(l, l+r>>1);
                    erase1(l+r>>1, r);
                    insert2(l, l+x>>1);
                    insert1(l+x>>1, x);
                    insert2(x, x+r>>1);
                    insert1(x+r>>1, r);
                }
            }
            S[now.k].insert(now.x);
        }
        else if(now.p==-1)
        {
            S[now.k].erase(S[now.k].find(now.x));
            if(S[now.k].find(now.x)==S[now.k].end())
            {
                if(S[now.k].size()==0)
                {
                    erase1(0, x);
                    erase2(x, 2e8);
                    chk--;
                }
                else if(S[now.k].size()==1)
                {
                    int l=*S[now.k].begin();
                    if(l<x)
                    {
                        insert2(l, 2e8);
                        erase2(l, l+x>>1);
                        erase1(l+x>>1, x);
                        erase2(x, 2e8);
                    }
                    else
                    {
                        insert1(0, l);
                        erase1(0, x);
                        erase2(x, l+x>>1);
                        erase1(l+x>>1, l);
                    }
                }
                else
                {
                    auto it=S[now.k].lower_bound(x);
                    int r=*it, l=*(--it);
                    insert2(l, l+r>>1);
                    insert1(l+r>>1, r);
                    erase2(l, l+x>>1);
                    erase1(l+x>>1, x);
                    erase2(x, x+r>>1);
                    erase1(x+r>>1, r);
                }
            }
        }
    }
    for(i=1; i<=Q; i++) printf("%d\n", ans[i]);
}

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp: In function 'int main()':
new_home.cpp:146:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                 scomp.insert(l+now.x>>1);
                              ~^~~~~~
new_home.cpp:147:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                 scomp.insert(r+now.x>>1);
                              ~^~~~~~
new_home.cpp:186:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert2(l, l+x>>1);
                                    ~^~
new_home.cpp:187:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert1(l+x>>1, x);
                                 ~^~
new_home.cpp:194:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert2(x, l+x>>1);
                                    ~^~
new_home.cpp:195:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         insert1(l+x>>1, l);
                                 ~^~
new_home.cpp:202:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     erase2(l, l+r>>1);
                               ~^~
new_home.cpp:203:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     erase1(l+r>>1, r);
                            ~^~
new_home.cpp:204:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     insert2(l, l+x>>1);
                                ~^~
new_home.cpp:205:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     insert1(l+x>>1, x);
                             ~^~
new_home.cpp:206:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     insert2(x, x+r>>1);
                                ~^~
new_home.cpp:207:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     insert1(x+r>>1, r);
                             ~^~
new_home.cpp:229:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase2(l, l+x>>1);
                                   ~^~
new_home.cpp:230:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase1(l+x>>1, x);
                                ~^~
new_home.cpp:237:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase2(x, l+x>>1);
                                   ~^~
new_home.cpp:238:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                         erase1(l+x>>1, l);
                                ~^~
new_home.cpp:245:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     insert2(l, l+r>>1);
                                ~^~
new_home.cpp:246:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     insert1(l+r>>1, r);
                             ~^~
new_home.cpp:247:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     erase2(l, l+x>>1);
                               ~^~
new_home.cpp:248:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     erase1(l+x>>1, x);
                            ~^~
new_home.cpp:249:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     erase2(x, x+r>>1);
                               ~^~
new_home.cpp:250:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                     erase1(x+r>>1, r);
                            ~^~
new_home.cpp:116:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
new_home.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &x, &t, &a, &b); b++; x*=2;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &l); x*=2;
         ~~~~~^~~~~~~~~~~~~~~~

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