제출 #439917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
439917		VladM	새 집 (APIO18_new_home)	C++14	12 / 100	2465 ms	42928 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

#define DIM 60007

#define KDIM 407

int n, m, k, ans[DIM], x, t, a, b, c, p, l, y, q;

pair<int, int> p1, p2;

struct event
{
    int x, p, t, c;
};

vector<event> Q;

set<pair<int, int> > s[KDIM];

bool cmp(event a, event b)
{
    if(a.t==b.t)
    {
        if(a.c==b.c) return a.x<b.x;
        return a.c<b.c;
    }
    return a.t<b.t;
}

int main()
{
    scanf("%d%d%d", &n, &k, &q);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d%d%d", &x, &t, &a, &b);
        Q.push_back({x, t, a, 0});
        Q.push_back({x, t, b, 2});
    }
    for(int i=1; i<=q; i++)
    {
        scanf("%d%d", &l, &y);
        Q.push_back({l, i, y, 1});
    }
    sort(Q.begin(), Q.end(), cmp);
    for(int i=0; i<Q.size(); i++)
    {
        x=Q[i].x;
        p=Q[i].p;
        t=Q[i].t;
        c=Q[i].c;
        //printf("%d %d %d %d\n", x, p, t, c);
        if(c==0) s[p].insert({x, i});
        if(c==2)
        {
            auto it=s[p].lower_bound({x, 0});
            s[p].erase(*it);
        }
        if(c==1)
        {
            if(s[1].empty())
            {
                ans[p]=-1;
                continue;
            }
            auto it=s[1].lower_bound({x, 0});
            auto it1=it;
            it1--;
            if(it==s[1].end())
            {
                p1=*it1;
                ans[p]=x-p1.first;
                //printf("%d\n", x-p1.first);
            }
            else if(it==s[1].begin())
            {
                p2=*it;
                ans[p]=p2.first-x;
                //printf("%d\n", p2.first-x);
            }
            else
            {
                p1=*it1;
                p2=*it;
                ans[p]=min(x-p1.first, p2.first-x);
                //printf("%d %d\n", x-p1.first, p2.first-x);
            }
            for(int i=2; i<=k; i++)
            {
                if(s[i].empty())
                {
                    ans[p]=-1;
                    break;
                }
                auto it=s[i].lower_bound({x, 0});
                auto it1=it;
                it1--;
                if(it==s[i].end())
                {
                    p1=*it1;
                    ans[p]=max(ans[p], x-p1.first);
                    //printf("%d\n", x-p1.first);
                }
                else if(it==s[i].begin())
                {
                    p2=*it;
                    ans[p]=max(ans[p], p2.first-x);
                    //printf("%d\n", p2.first-x);
                }
                else
                {
                    p1=*it1;
                    p2=*it;
                    ans[p]=max(ans[p], min(x-p1.first, p2.first-x));
                    //printf("%d %d\n", x-p1.first, p2.first-x);
                }
            }
        }
    }
    for(int i=1; i<=q; i++) printf("%d\n", ans[i]);
    return 0;
}

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

new_home.cpp: In function 'int main()':
new_home.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0; i<Q.size(); i++)
      |                  ~^~~~~~~~~
new_home.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d%d%d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d%d%d", &x, &t, &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d%d", &l, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

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