Submission #401986

#	Time	Username	Problem	Language	Result	Execution time	Memory
401986		teehandsome	New Home (APIO18_new_home)	C++17	12 / 100	5060 ms	51532 KiB

new_home

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct dt {
    int s,t,x;
    dt(int S,int T,int X) {
        s=S,t=T,x=X;
    }
};
bool operator<(const dt &l,const dt &r) {
    if(l.x==r.x) {
        if(l.s==r.s) return l.t<r.t;
        return l.s<r.s;
    }
    return l.x<r.x;
}

const int mxn=3e5+10;
int n,q,k;
vector<dt> a[mxn];
vector<dt> av[mxn];

#define fi first
#define se second

void deebug(vector<dt> ar) {
    int len=ar.size();
    cout<<"------"<<endl;
    for(int i=0;i<len;i++) {
        cout<<ar[i].s<<" "<<ar[i].t<<" "<<ar[i].x<<endl;
    }
    cout<<"====="<<endl;
}

int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>k>>q;
    for(int i=0;i<n;i++) {
        int x,tt,u,v;
        cin>>x>>tt>>u>>v;
        a[tt].push_back({u,v,x});
    }
    for(int i=1;i<=k;i++) {
        av[i]=a[i];
        sort(all(a[i]),[&](const dt &l,const dt &r) {
                if(l.s==r.s) return l.t<r.t;
                return l.s<r.s;
             });
        sort(all(av[i]),[&](const dt &l,const dt &r) {
                return l.t<r.t;
             });
    }

    vector<int> ans(q);
    vector<ppi> que(q);
    // {time , {pos,idx}}
    for(int i=0;i<q;i++) {
        cin>>que[i].se.fi>>que[i].fi;
        que[i].se.se=i;
    }
    sort(all(que));
    vector<int> lu(k+1,0),lv(k+1,0);
    multiset<dt> s[k+1];
//    for(int i=1;i<=k;i++) {
//        deebug(a[i]);
//        deebug(av[i]);
//    }

    for(int i=0;i<q;i++) {
        int t=que[i].fi;
        int idx=que[i].se.se;
        int pos=que[i].se.fi;
//        debug(i,t,pos,idx);
        int mx=0;
        bool ok=true;

        for(int j=1;j<=k;j++) {
            int sz=a[j].size();
            while(lu[j]<sz and a[j][lu[j]].s<=t) {
                s[j].insert(a[j][lu[j]]);
                lu[j]++;
            }
            while(lv[j]<sz and av[j][lv[j]].t<t) {
                auto temp=s[j].find(av[j][lv[j]]);
                if(temp!=s[j].end()) s[j].erase(s[j].find(av[j][lv[j]]));
                else assert(false);
                lv[j]++;
            }
//            debug(j,lu[j],lv[j]);
            if(s[j].empty()) ok=false;
            else {
//                for(auto e:s[j]) {
//                    cout<<"# "<<e.x<<" "<<e.s<<" "<<e.t<<endl;
//                }
                dt temp(-1,-1,pos);
                auto pp1=s[j].lower_bound(temp);
                auto pp2=pp1; --pp2;
                dt p1(0,0,INF),p2(0,0,INF);
                if(pp1!=s[j].end()) p1=*pp1;
                if(pp2!=s[j].end()) p2=*pp2;
//                cout<<"% "<<p1.x<<" "<<p1.s<<" "<<p1.t<<endl;
//                cout<<"% "<<p2.x<<" "<<p2.s<<" "<<p2.t<<endl;
//                cout<<p1.x<<","<<p2.x<<endl;
                int d=min(abs(p1.x-pos),abs(p2.x-pos));
//                debug(j,d);
                mx=max(mx,d);
            }
        }
        if(!ok) ans[idx]=-1;
        else ans[idx]=mx;
    }
    for(int i=0;i<q;i++) {
        cout<<ans[i]<<endl;
    }
}

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