Submission #742339

#	Time	Username	Problem	Language	Result	Execution time	Memory
742339		victor_gao	New Home (APIO18_new_home)	C++17	0 / 100	53 ms	34168 KiB

new_home

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 60015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,q,k,x[N],t[N],a[N],b[N],l[N],y[N],ans[N];
multiset<int>st[505];
vector<pii>in[3*N],out[3*N],qry[3*N];
struct lisan{
    vector<int>vt;
    void in(int x){ vt.push_back(x); }
    void build(){
        sort(vt.begin(),vt.end());
        vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    }
    int idx(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
}uni;
signed main(){
    fast
    cin>>n>>k>>q;
    for (int i=1;i<=n;i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
        uni.in(a[i]); uni.in(b[i]+1);
    }
    for (int i=1;i<=q;i++){
        cin>>l[i]>>y[i];
        uni.in(y[i]);
    }
    uni.build();
    for (int i=1;i<=n;i++){
        in[uni.idx(a[i])].push_back({x[i],t[i]});
        out[uni.idx(b[i]+1)].push_back({x[i],t[i]});
    }
    for (int i=1;i<=q;i++){
        qry[uni.idx(y[i])].push_back({l[i],i});
    }
    for (int i=0;i<3*N;i++){
        for (auto j:out[i]){
            st[j.y].erase(st[j.y].find(j.x));
        }
        for (auto j:in[i]){
            st[j.y].insert(j.x);
        }
        for (auto [p,i]:qry[i]){
            int tans=-1;
            for (int j=1;j<=k;j++){
                if (st[j].empty()){
                    tans=-1;
                    break;
                }
                auto it=st[j].lower_bound(p);
                if (it==st[j].begin()) tans=max(tans,(*it)-p);
                else if (it==st[j].end()){
                    it=prev(it);
                    tans=max(tans,(*it)-p);
                }
                else {
                    auto it1=prev(it);
                    tans=max(tans,min((*it)-p,p-(*it1)));
                }
            }
            ans[i]=tans;
        }
    }
    for (int i=1;i<=q;i++)
        cout<<ans[i]<<"\n";
}

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