제출 #1170693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170693		danglayloi1	새 집 (APIO18_new_home)	C++20	12 / 100	5094 ms	50020 KiB

new_home

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=3e5+5;
int n, k, q, ans[nx];
struct dak
{
    int x, t, a, b;
} a[nx];
multiset<int> pos;
vector<int> rar, type[nx], st[nx], en[nx], qu[nx];
ii f[nx];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k>>q;
    for(int i = 1; i <= n; i++)
        cin>>a[i].x>>a[i].t>>a[i].a>>a[i].b, type[a[i].t].emplace_back(i);
    for(int i = 1; i <= q; i++)
        cin>>f[i].fi>>f[i].se, ans[i]=-1;
    for(int id = 1; id <= k; id++)
    {
        rar.clear();
        for(int i:type[id])
            rar.emplace_back(a[i].a), rar.emplace_back(a[i].b);
        for(int i = 1; i <= q; i++)
            if(ans[i]!=-2) rar.emplace_back(f[i].se);
        sort(rar.begin(), rar.end());
        rar.erase(unique(rar.begin(), rar.end()), rar.end());
        for(int i = 0; i <= rar.size(); i++)
            st[i].clear(), en[i].clear(), qu[i].clear();
        for(int i:type[id])
        {
            int x=upper_bound(rar.begin(), rar.end(), a[i].a)-rar.begin();
            st[x].emplace_back(i);
            x=upper_bound(rar.begin(), rar.end(), a[i].b)-rar.begin();
            en[x].emplace_back(i);
        }
        for(int i = 1; i <= q; i++)
        {
            if(ans[i]==-2) continue;
            int x=upper_bound(rar.begin(), rar.end(), f[i].se)-rar.begin();
            qu[x].emplace_back(i);
        }
        pos.clear();
        for(int i = 1; i <= rar.size(); i++)
        {
            for(int j:st[i])
                pos.emplace(a[j].x);
            for(int j:qu[i])
            {
                auto it=pos.lower_bound(f[j].fi);
                int cur=inf;
                if(it!=pos.end()) cur=min(cur, *it-f[j].fi);
                if(it!=pos.begin()) it--, cur=min(cur, f[j].fi-*it);
                if(cur==inf) ans[j]=-2;
                else ans[j]=max(ans[j], cur);
            }
            for(int j:en[i])
                pos.erase(pos.find(a[j].x));
        }
    }
    for(int i = 1; i <= q; i++)
        cout<<max(-1, ans[i])<<'\n';
}

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