Submission #552454

#	Time	Username	Problem	Language	Result	Execution time	Memory
552454		zaneyu	New Home (APIO18_new_home)	C++14	12 / 100	5093 ms	56224 KiB

new_home

/*input
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
*/
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma target("avx3")
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
const int maxn=3e5+5;
#define pb push_back
#define lowb(x) x&(-x)
#define ll long long
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pii pair<int,int>
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define sz(x) (int)x.size()
int ans[maxn];
multiset<int> s[maxn];
const int INF=0x3f3f3f3f;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,k,q;
    cin>>n>>k>>q;
    vector<pair<pii,pii>> v;
    vector<pair<pii,int>> qq;
    REP(i,n){
        int x,t,a,b;
        cin>>x>>t>>a>>b;
        v.pb({{a,1},{x,t}});
        v.pb({{b+1,-1},{x,t}});
    }
    REP(i,q){
        int p,y;
        cin>>p>>y;
        qq.pb({{y,p},i});
    }
    sort(ALL(v)),sort(ALL(qq));
    int p=0;
    for(auto x:qq){
        while(p<sz(v) and v[p].f.f<=x.f.f){
            if(v[p].f.s==1){
                s[v[p].s.s].insert(v[p].s.f);
            }
            else{
                s[v[p].s.s].erase(s[v[p].s.s].find(v[p].s.f));
            }
            ++p;
        }
        int mx=0;
        REP1(i,k){
            auto it=s[i].lower_bound(x.f.s);
            int cur=INF;
            if(it!=s[i].end()) MNTO(cur,(*it)-x.f.s);
            if(it!=s[i].begin()){
                --it;
                MNTO(cur,x.f.s-(*it));
            }
            MXTO(mx,cur);
        }
        if(mx==INF) ans[x.s]=-1;
        else ans[x.s]=mx;
    }
    REP(i,q) cout<<ans[i]<<'\n';
}

Compilation message (stderr)

new_home.cpp:14: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
   14 | #pragma target("avx3")
      |

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