제출 #60147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60147		duality	새 집 (APIO18_new_home)	C++11	45 / 100	5031 ms	372416 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[300000];
int ans[300000];
map<int,int> M;
int query(int x) {
    auto it = M.lower_bound(x);
    int m = 0;
    if (it != M.end()) m = max(m,it->second-(it->first-x));
    if (it != M.begin()) it--,m = max(m,it->second-(x-it->first));
    return m;
}
int update(int x,int h) {
    //cout<<"UPDATE "<<x<<","<<h<<endl;
    if (query(x) >= h) return 0;
    //cout<<"XXX"<<endl;
    auto it = M.lower_bound(x);
    while (it != M.end()) {
        if (it->second > h-(it->first-x)) break;
        else it = M.erase(it);
    }
    M[x] = h;
    it = M.find(x);
    while (1) {
        if (it == M.begin()) break;
        it--;
        if (it->second > h-(x-it->first)) break;
        else it = M.erase(it);
    }
    return 0;
}
int main() {
    int i;
    int n,k,q;
    int x,t,a,b,l,y;
    int sub34 = 1;
    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});
        sub34 &= (a == 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;
    if (sub34) {
        int f = 0;
        for (i = 0; i < oper.size(); i++) {
            if (oper[i].t > 0) stores[oper[i].t-1].insert(oper[i].x);
            else {
                if (!f) {
                    //cout<<"here"<<endl;
                    for (j = 0; j < k; j++) {
                        stores[j].insert(-3e8);
                        stores[j].insert(3e8);
                        for (auto it = ++stores[j].begin(); it != stores[j].end(); it++) {
                            auto it2 = it;
                            it2--;
                            update(*it+*it2,*it-*it2);
                        }
                    }
                    f = 1;
                    //for (auto it = M.begin();it!=M.end();it++){
                    //    cout<<it->first<<","<<it->second<<endl;
                    //}
                }
                if (oper[i].t < 0) {
                    int p = -oper[i].t-1;
                    auto it = stores[p].find(oper[i].x);
                    auto it2 = it;
                    it++,it2--;
                    update(*it+*it2,*it-*it2);
                    stores[p].erase(stores[p].find(oper[i].x));
                }
                else {
                    ans[oper[i].i] = query(2*oper[i].x)/2;
                    if (ans[oper[i].i] > 1e8) ans[oper[i].i] = -1;
                }
            }
        }
    }
    else {
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

new_home.cpp: In function 'int main()':
new_home.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < oper.size(); i++) {
                     ~~^~~~~~~~~~~~~
new_home.cpp:101:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < oper.size(); i++) {
                     ~~^~~~~~~~~~~~~
new_home.cpp:50: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:52: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:58: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: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20