Submission #784365

#	Time	Username	Problem	Language	Result	Execution time	Memory
784365		1075508020060209tc	New Home (APIO18_new_home)	C++14	12 / 100	5097 ms	281812 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;
int K;int Q;
int xar[500005];
int typ[500005];
int ta[500005];
int tb[500005];
int qpl[500005];
int qt[500005];
int ans[500005];
void lisanhua(){
vector<int>vc;
for(int i=1;i<=n;i++){
    vc.push_back(ta[i]);
    vc.push_back(tb[i]);
}
for(int i=1;i<=Q;i++){
    vc.push_back(qt[i]);
}
sort(vc.begin(),vc.end());
for(int i=1;i<=n;i++){
    ta[i]=1+(lower_bound(vc.begin(),vc.end(),ta[i])-vc.begin());
    tb[i]=1+(lower_bound(vc.begin(),vc.end(),tb[i])-vc.begin());
}
for(int i=1;i<=Q;i++){
    qt[i]=1+(lower_bound(vc.begin(),vc.end(),qt[i])-vc.begin());
}
}
multiset<int>mst[510];
struct SGTR{
int l;int r;
vector<pair<int,int>>eve;
}tr[2000006];
void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
if(l==r){return;}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
}

void upd(int nw,int l,int r,pair<int,int>shp){
if(tr[nw].l>=l&&tr[nw].r<=r){
    tr[nw].eve.push_back(shp);
    return;
}
if(tr[nw].r<l||tr[nw].l>r){
    return;
}
upd(nw*2,l,r,shp);
upd(nw*2+1,l,r,shp);
}
vector<int>fq[1000006];
void dfs(int nw){
for(int i=0;i<tr[nw].eve.size();i++){
    int tk=tr[nw].eve[i].second;
    int tpl=tr[nw].eve[i].first;
    mst[tk].insert(tpl);
}
if(tr[nw].l==tr[nw].r){
    int nwpl=tr[nw].l;
    for(int iid=0;iid<fq[nwpl].size();iid++){
        int id=fq[nwpl][iid];
        int pl=qpl[id];
        for(int k=1;k<=K;k++){
            auto it=mst[k].lower_bound(pl);
            int v=abs((*it)-pl);
            it=prev(it);
            int vv=abs((*it)-pl);
            ans[id]=max(ans[id],min(v,vv));
        }
    }
}else{
    dfs(nw*2);
    dfs(nw*2+1);
}
for(int i=0;i<tr[nw].eve.size();i++){
    int tk=tr[nw].eve[i].second;
    int tpl=tr[nw].eve[i].first;
    mst[tk].erase(mst[tk].find(tpl) );
}


}

signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>K>>Q;
    for(int i=1;i<=K;i++){
        mst[i].insert(-2e9);
        mst[i].insert(2e9);
    }
    for(int i=1;i<=n;i++){
        cin>>xar[i]>>typ[i]>>ta[i]>>tb[i];
    }
    for(int i=1;i<=Q;i++){
        cin>>qpl[i]>>qt[i];
    //    ansl[i]=0;ansr[i]=1e9;
    }
    lisanhua();
    buildtr(1,1,500005);
    for(int i=1;i<=n;i++){
        upd(1,ta[i],tb[i],{xar[i],typ[i]});
    }
    for(int i=1;i<=Q;i++){
        fq[qt[i]].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=Q;i++){
        if(ans[i]>=1e9){
            cout<<-1<<endl;
        }else{
            cout<<ans[i]<<endl;
        }
    }

}


/*
int kcnt;
int freq[500005];
void add(int v){
freq[v]++;
if(freq[v]==1){
    kcnt++;
}
}
void del(int v){
freq[v]--;
if(freq[v]==0){
    kcnt--;
}
}
*/

Compilation message (stderr)

new_home.cpp: In function 'void dfs(long long int)':
new_home.cpp:59:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 | for(int i=0;i<tr[nw].eve.size();i++){
      |             ~^~~~~~~~~~~~~~~~~~
new_home.cpp:66:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int iid=0;iid<fq[nwpl].size();iid++){
      |                   ~~~^~~~~~~~~~~~~~~~
new_home.cpp:81:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 | for(int i=0;i<tr[nw].eve.size();i++){
      |             ~^~~~~~~~~~~~~~~~~~

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