Submission #106801

#	Time	Username	Problem	Language	Result	Execution time	Memory
106801		tictaccat	New Home (APIO18_new_home)	C++14	12 / 100	5075 ms	45112 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

const int MAX = 3e5 + 10;
const int INF = 1e9;

int n,k,q;

vector<set<pair<int,int>>> types(MAX);
vector<tuple<int,int,int,int,int>> events;
vector<tuple<int,int,int>> queries;
vector<int> answers(MAX);

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> k >> q;

    for (int i = 0; i < n; i++) {
        int x,t,a,b; cin >> x >> t >> a >> b;
        events.emplace_back(a,i,x,t,1);
        events.emplace_back(b+1,i,x,t,-1);
    }   

    for (int query = 0; query < q; query++) {
        int l,y; cin >> l >> y; 
        queries.push_back(make_tuple(y,l,query));
    }

    sort(events.begin(),events.end());
    sort(queries.begin(),queries.end());
    int p = 0;

    for (int z = 0; z < q; z++) {
       // cout << "z: " << z << "\n";
        int y,l,query; tie(y,l,query) = queries[z];
        while (p < events.size() && get<0>(events[p]) <= y) {
            int time,i,x,type,change; tie(time,i,x,type,change) = events[p];
            if (change == 1) {
                types[type].insert(make_pair(x,i));
                //cout << "adding: " << type << " " << x << " " << i << "\n";
            }
            if (change == -1) {
                //cout << "removing: " << type << " " << x << " " << i << "\n";
                assert(types[type].count(make_pair(x,i)) == 1);
                types[type].erase(make_pair(x,i));
            }
            p++;
        }
        int far = 0;
        for (int type = 1; type <= k; type++) {
            if (types[type].size() == 0) {
               // cout << type << "\n";
                far = -1;
                break;
            }
            auto itRight = types[type].lower_bound(make_pair(l,-1));
            int dist = INF;
            if (itRight != types[type].end()) {
                dist = min(dist,(*itRight).first - l);
                assert((*itRight).first - l >= 0);
            }
            if (itRight != types[type].begin()) {
                auto itLeft = prev(itRight);
                dist = min(dist,l-(*itLeft).first);
                assert(l-(*itLeft).first >= 0);
            }
            far = max(far,dist);
        }
        answers[query] = far;
    }

    for (int query = 0; query < q; query++) cout << answers[query] << "\n";

    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (p < events.size() && get<0>(events[p]) <= y) {
                ~~^~~~~~~~~~~~~~~

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