Submission #710011

#	Time	Username	Problem	Language	Result	Execution time	Memory
710011		vjudge1	New Home (APIO18_new_home)	C++17	12 / 100	5048 ms	64240 KiB

new_home

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<ii,ii> iiii;
#define ff first
#define ss second

const int maxn = 3e5 + 10;
int n,k,m;
multiset<int> ms[maxn];
vector <iiii> d;
int res[maxn];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>k>>m;
    for (int i=1; i<=n; i++)
    {
        int x,y,l,r; cin>>x>>y>>l>>r;
        d.push_back({{l,-1},{x,y}});
        d.push_back({{r,1},{x,y}});
    }
    for (int i=1; i<=m; i++)
    {
        int x,l; cin>>x>>l;
        d.push_back({{l,0},{x,i}});
    }
    sort(d.begin(),d.end());
    for (iiii i:d)
    {
//        cout<<i.ff.ff<<' '<<i.ff.ss<<" : "<<i.ss.ff<<' '<<i.ss.ss<<endl;
        if (i.ff.ss == -1) ms[i.ss.ss].insert(i.ss.ff);
        else if (i.ff.ss == 1) ms[i.ss.ss].erase(ms[i.ss.ss].find(i.ss.ff));
        else
        {
            bool check = 1;
            int ans = 0;
            for (int j=1; j<=k; j++) if (!ms[j].empty())
            {
                int temp = 1e9;
                auto x = ms[j].upper_bound(i.ss.ff);
                if (x!=ms[j].end()) temp = min(temp , (*x) - i.ss.ff);
                if (x!=ms[j].begin())
                {
                    x--;
                    temp = min(temp, i.ss.ff - (*x));
                }
                ans = max(ans,temp);
            }
            else
            {
                check=0;
                break;
            }
            if (check) res[i.ss.ss] = ans;
            else res[i.ss.ss] = -1;
        }
    }
    for (int i=1; i<=m; i++) cout<<res[i]<<'\n';
}
/**
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
**/

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