Submission #60139

#	Time	Username	Problem	Language	Result	Execution time	Memory
60139		duality	새 집 (APIO18_new_home)	C++11	12 / 100	3606 ms	87552 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

struct op { int time,t,x,i; };
bool comp(op a,op b) {
    if (a.time == b.time) return a.t > b.t;
    else return a.time < b.time;
}
vector<op> oper;
multiset<int> stores[400];
int ans[300000];
int main() {
    int i;
    int n,k,q;
    int x,t,a,b,l,y;
    scanf("%d %d %d",&n,&k,&q);
    for (i = 0; i < n; i++) {
        scanf("%d %d %d %d",&x,&t,&a,&b);
        oper.pb((op){a,t,x,-1});
        oper.pb((op){b,-t,x,-1});
    }
    for (i = 0; i < q; i++) {
        scanf("%d %d",&l,&y);
        oper.pb((op){y,0,l,i});
    }
    sort(oper.begin(),oper.end(),comp);

    int j;
    for (i = 0; i < oper.size(); i++) {
        if (oper[i].t > 0) stores[oper[i].t-1].insert(oper[i].x);
        else if (oper[i].t < 0) stores[-oper[i].t-1].erase(stores[-oper[i].t-1].find(oper[i].x));
        else {
            int m = 0;
            for (j = 0; j < k; j++) {
                if (stores[j].empty()) break;
                else {
                    auto it = stores[j].lower_bound(oper[i].x);
                    int mm = 1e9;
                    if (it != stores[j].end()) mm = min(mm,*it-oper[i].x);
                    if (it != stores[j].begin()) mm = min(mm,oper[i].x-*(--it));
                    m = max(m,mm);
                }
            }
            if (j < k) ans[oper[i].i] = -1;
            else ans[oper[i].i] = m;
        }
    }
    for (i = 0; i < q; i++) printf("%d\n",ans[i]);

    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < oper.size(); i++) {
                 ~~^~~~~~~~~~~~~
new_home.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&n,&k,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&x,&t,&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         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