Submission #60019

#	Time	Username	Problem	Language	Result	Execution time	Memory
60019		istlemin	New Home (APIO18_new_home)	C++14	0 / 100	2076 ms	73240 KiB

new_home

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

int main(){
	cin.sync_with_stdio(false);
    ll n,q,k;
    cin>>n>>k>>q;
    vi sx(n);
    vi st(n);
    vi sa(n);
    vi sb(n);
	rep(i,0,n){
		cin>>sx[i]>>st[i]>>sa[i]>>sb[i];
		--st[i];
	}
    vector<vi> shops(k);
    rep(i,0,n){
		shops[st[i]].push_back(sx[i]);
    }

    vi l(q);
    vi y(q);
    rep(i,0,q) cin>>l[i]>>y[i];

    vector<tuple<ll,ll,ll> > events;

	rep(i,0,k){
		sort(all(shops[i]));
        rep(j,0,shops[i].size()){
			if(j!=0&&shops[i][j-1]!=shops[i][j]){
				events.emplace_back((shops[i][j-1]+shops[i][j])/2,st[i],1);
			}
			events.emplace_back(shops[i][j],i,0);
        }
	}

    rep(i,0,q) {
		events.emplace_back(l[i],i,2);
    }


    sort(all(events));

    vi posLeft(k);
    vi posRight(k);

	set<pii> left;
	set<pii> right;

	rep(i,0,k){
        posLeft[i] = 1e18;
        if(shops[i].size()==0){
			rep(i,0,q) cout<<-1<<endl;
            _Exit(0);
        }
        posRight[i] = shops[i][0];
        right.insert({shops[i][0],i});
	}

	vi qAns(q);

    rep(i,0,events.size()){
		ll x,t,a;
		tie(x,t,a) = events[i];
        if(a==0){
            right.erase({posRight[t],t});
            posLeft[t] = x;
            left.insert({posLeft[t],t});
        }
        if(a==1){
            left.erase({posLeft[t],t});
            posRight[t] = *upper_bound(all(shops[t]),x);
            right.insert({posRight[t],t});
        }
        if(a==2){
			qAns[t] = 0;
			if(left.size())
				qAns[t] = max(qAns[t],x-left.begin()->first);
			if(right.size())
				qAns[t] = max(qAns[t],prev(right.end())->first - x);
        }
    }
    rep(i,0,q) cout<<qAns[i]<<endl;


}

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