Submission #394005

#	Time	Username	Problem	Language	Result	Execution time	Memory
394005		79brue	New Home (APIO18_new_home)	C++14	12 / 100	2380 ms	43960 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Mart{
    int x, y, t; bool on; /// location, type, time
    Mart(int x, int y, int t, bool on): x(x), y(y), t(t), on(on){}
    bool operator<(const Mart &r)const{
        return t<r.t;
    }
};

struct Query{
    int x, t, idx;
    Query(){}
    Query(int x, int t, int idx): x(x), t(t), idx(idx){}
    bool operator<(const Query &r)const{
        return t<r.t;
    }
};

int n, q, k;
vector<Mart> vec;
vector<Query> qvec;
multiset<int> mst[402];

int ans[300002];

int main(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<=n; i++){
        int x, t, a, b;
        scanf("%d %d %d %d", &x, &t, &a, &b);
        vec.push_back(Mart(x, t, a, 1));
        vec.push_back(Mart(x, t, b+1, 0));
    }
    sort(vec.begin(), vec.end());

    for(int i=1; i<=q; i++){
        int l, y;
        scanf("%d %d", &l, &y);
        qvec.push_back(Query(l, y, i));
    }
    sort(qvec.begin(), qvec.end());

    int pnt = 0;
    for(int i=0; i<q; i++){
        while(pnt < 2*n && vec[pnt].t <= qvec[i].t){
            Mart tmp = vec[pnt++];
            if(tmp.on) mst[tmp.y].insert(tmp.x);
            else mst[tmp.y].erase(mst[tmp.y].find(tmp.x));
        }

        for(int j=1; j<=k; j++){
            auto it = mst[j].lower_bound(qvec[i].x);
            int tmp = INT_MAX;
            if(it != mst[j].end()) tmp = min(tmp, *it - qvec[i].x);
            if(it != mst[j].begin()) tmp = min(tmp, qvec[i].x - *prev(it));
            ans[qvec[i].idx] = max(ans[qvec[i].idx], tmp);
        }
    }

    for(int i=1; i<=q; i++) printf("%d\n", ans[i] == INT_MAX ? -1 : ans[i]);
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |         scanf("%d %d %d %d", &x, &t, &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |         scanf("%d %d", &l, &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