Submission #698922

#	Time	Username	Problem	Language	Result	Execution time	Memory
698922		vjudge1	New Home (APIO18_new_home)	C++17	5 / 100	5031 ms	74640 KiB

new_home

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
int mod=1e9+7;
const int N=1e5+5;
template<class x>
using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(".in", "r", stdin); freopen(".out", "w", stdout);

    int n,k,q; cin>>n>>k>>q;
    vector<pair<int,pair<int,pair<int,int> > > > v;
    for (int i=0;i<n;i++) {
      int a,b,c,d; cin>>a>>b>>c>>d;
      v.push_back({c,{0,{a,b}}});
      v.push_back({d,{2,{a,b}}});
    }
    for (int i=0;i<q;i++) {
      int l,y; cin>>l>>y;
      v.push_back({y,{1,{l,i}}});
    }
    sort(v.begin(),v.end());

    int ans[q];
    int dis[k];
    for (int i=0;i<q;i++) ans[i]=-1;

    set<int> st[k];
    map<pair<int,int>,int> mp;
    for (int i=0;i<v.size();i++) {
      if (v[i].second.first==0) {
        int lc=v[i].second.second.first,tp=v[i].second.second.second;
        if (mp[{lc,tp}]==0) st[tp-1].insert(lc);
        mp[{lc,tp}]++;
      }
      else if (v[i].second.first==1) {
        int lc=v[i].second.second.first,indx=v[i].second.second.second;
         for (int j=0;j<k;j++) {
           auto nm=st[j].lower_bound(lc);
           int lf=-1,rg=-1;
           if (mp[{*nm,j+1}]>0 && *nm>=lc) rg=abs(*nm-lc);
           if (nm!=st[j].begin()) {nm--; lf=abs(lc-*nm);}
           if (lf==-1) {
             if (rg==-1) dis[j]=-1;
             else dis[j]=rg;
           }
           else {
             if (rg==-1) dis[j]=lf;
             else dis[j]=min(lf,rg);
           }
           if (dis[j]==-1) break;
         }

        int mx=0;
        for (int j=0;j<k;j++) {
          if (dis[j]==-1) {mx=-1; break;}
          mx=max(mx,dis[j]);
        }
        ans[indx]=mx;
      }
      else {
        int lc=v[i].second.second.first,tp=v[i].second.second.second;
        mp[{lc,tp}]--;
        if (mp[{lc,tp}]==0) st[tp-1].erase(lc);
      }
    }

    for (int i=0;i<q;i++) cout<<ans[i]<<endl;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i=0;i<v.size();i++) {
      |                  ~^~~~~~~~~

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