제출 #365305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365305		doowey	New Home (APIO18_new_home)	C++14	0 / 100	5146 ms	806744 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 10;
const int M = N * 4;
int x[N];
int a[N];
int b[N];
int t[N];

vector<int> bb;

multiset <int> P[N];

int cum;

void add(int id, int v){ // = 2n points
    bb.push_back(v);
    auto it = P[id].insert(v);
    auto nx = it;
    nx ++ ;
    if(nx != P[id].end()){
        cum = v + (*nx);
        if(cum % 2 == 0){
            bb.push_back(cum/2);
        }
        else{
            bb.push_back(cum/2);
            bb.push_back(cum/2+1);
        }
    }
    nx = it;
    if(nx != P[id].begin()){
        nx -- ;
        cum = v + (*nx);
        if(cum % 2 == 0){
            bb.push_back(cum/2);
        }
        else{
            bb.push_back(cum/2);
            bb.push_back(cum/2+1);
        }
    }
}

void delet(int id, int v){
    auto it = P[id].lower_bound(v);
    auto nx = it;
    nx ++ ;
    auto pv = it;
    if(pv != P[id].begin() && nx != P[id].end()){
        cum = (*pv + *nx);
        pv--;
        if(cum % 2 == 0){
            bb.push_back(cum/2);
        }
        else{
            bb.push_back(cum/2);
            bb.push_back(cum/2+1);
        }
    }
    P[id].erase(it);
}


multiset<int> Q[2][M*4+12];

void ins(int node, int cl, int cr, int tl, int tr, int dir, int v, int mode){
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        if(mode == 0)
            Q[dir][node].insert(v);
        else
            Q[dir][node].erase(Q[dir][node].find(v));
        return;
    }
    int mid = (cl + cr) / 2;
    ins(node * 2, cl, mid, tl, tr, dir, v, mode);
    ins(node * 2 + 1, mid + 1, cr, tl, tr, dir, v, mode);
}

int get(int node, int cl, int cr, int pos){
    int vl = 0;
    if(!Q[0][node].empty()){ // O(1) ????????
        auto it = Q[0][node].end();
        -- it;
        vl = max(vl, bb[pos]+*it);
    }
    if(!Q[1][node].empty()){
        auto it = Q[1][node].end();
        -- it;

        vl=max(vl,*it-bb[pos]);
    }
    if(cl == cr) return vl;
    int mid = (cl + cr) / 2;
    if(mid >= pos)
        vl = max(vl, get(node*2,cl,mid,pos));
    else
        vl=max(vl, get(node*2+1,mid+1,cr,pos));
    return vl;
}

int ln[N];
int yr[N];

int cnt[N];
int tot;

int getid(int ff){
    return lower_bound(bb.begin(), bb.end(), ff) - bb.begin();
}

int m;

void add_f(int li, int ri, int mode){
    if(li == -(int)1e9 && ri == (int)1e9) return;
    cum = (li + ri);
    if(cum % 2 == 0){
        ins(1, 0, m - 1, getid(li), getid(cum/2),0,-li,mode);
        ins(1, 0, m - 1, getid(cum/2), getid(ri),1,ri,mode);
    }
    else{
        ins(1, 0, m - 1, getid(li), getid(cum/2),0,-(li),mode);
        ins(1, 0, m - 1, getid(cum/2+1), getid(ri),1,(ri),mode);
    }
}

int soln[N];

int main(){
    fastIO;
    int n, k, q;
    cin >> n >> k >> q;
    vector<pii> eve;
    for(int i = 1; i <= n; i ++ ){
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        eve.push_back(mp(a[i], i));
        eve.push_back(mp(b[i] + 1, i));
    }
    sort(eve.begin(), eve.end());
    for(int i = 1; i <= k ; i ++ ){
        P[i].insert(-(int)1e9);
        P[i].insert((int)1e9);
    }
    bb.push_back(-(int)1e9);
    bb.push_back((int)1e9); // logs stay ~ the same doesn't make a diff
    for(auto q : eve){
        if(q.fi == a[q.se]){
            add(t[q.se], x[q.se]);
        }
        else{
            delet(t[q.se], x[q.se]);
        }
    }
    vector<pii> qq;
    for(int i = 1; i <= q; i ++ ){
        cin >> ln[i] >> yr[i];
        qq.push_back(mp(yr[i], i));
        bb.push_back(ln[i]);
    }
    bb.push_back(0);

    sort(bb.begin(), bb.end());
    bb.resize(unique(bb.begin(), bb.end()) - bb.begin());
    m = bb.size();
    sort(qq.begin(), qq.end());
    int iq = 0;
    int id;
    for(auto p : qq){
        while(iq < eve.size() && eve[iq].fi <= p.fi){
            id = eve[iq].se;
            if(eve[iq].fi == a[eve[iq].se]){
                cnt[t[id]] ++ ;
                if(cnt[t[id]] == 1) tot ++ ;
                auto it = P[t[id]].insert(x[id]);
                auto pv = it;
                auto nx = it;
                nx ++ ;
                if(nx != P[t[id]].end()){
                    add_f(*it, *nx, 0);
                }
                if(pv != P[t[id]].begin()){
                    pv -- ;
                    add_f(*pv, *it, 0);
                }
            }
            else{
                cnt[t[id]] -- ;
                if(cnt[t[id]] == 0) tot -- ;
                auto it = P[t[id]].lower_bound(x[id]);
                auto pv = it;
                auto nx = it;
                nx ++ ;
                bool big = true;
                if(nx != P[t[id]].end()){
                    add_f(*it, *nx, 1);
                }
                else big = false;
                if(pv != P[t[id]].begin()){
                    pv -- ;
                    add_f(*pv, *it, 1);
                }
                else big = false;
                if(big){
                    add_f(*pv, *nx, 0);
                }
                P[t[id]].erase(it);
            }
            iq ++ ;
        }
        if(tot == k){
            soln[p.se]=get(1, 0, m - 1, getid(ln[p.se]));
        }
        else{
            soln[p.se]=-1;
        }
    }
    for(int i = 1; i <= q; i ++ ){
        cout << soln[i] << "\n";
    }
    return 0;
}

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

new_home.cpp: In function 'int main()':
new_home.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         while(iq < eve.size() && eve[iq].fi <= p.fi){
      |               ~~~^~~~~~~~~~~~

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