Submission #1240566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240566		HuyAT	New Home (APIO18_new_home)	C++17	0 / 100	5101 ms	169060 KiB

new_home

#include<bits/stdc++.h>
#define newl '\n'

const int N = 3e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

struct FenwickTree{
    std::vector<int> bit;
    FenwickTree(int n) : bit(n + 1,0){

    }
    void update(int idx,int v){
        for(int i = idx;i < (int)bit.size();i += (i & (-i))){
            bit[i] += v;
        }
    }
    int sum(int idx){
        int ans = 0;
        for(int i = idx;i > 0;i -= (i & (-i))){
            ans += bit[i];
        }
        return ans;
    }
    int query(int l,int r){
//        std::cerr << "1D bit query " << l << " " << r << newl;
        return sum(r) - sum(l - 1);
    }
};
struct FenwickTree2D{
    std::vector<std::vector<int>> bit,com;
    FenwickTree2D(int n) : bit(n + 1),com(n + 1){

    }
    void fake_update(int x,int y){
//        std::cerr << "bit2d fake_update " << x << " " << y << newl;
        for(int i = x;i < (int)com.size();i += (i & (-i))){
            com[i].emplace_back(y);
        }
    }
    void prepare(){
        for(int i = 1;i < (int)bit.size();++i){
            std::sort(com[i].begin(),com[i].end());
            com[i].erase(std::unique(com[i].begin(),com[i].end()),com[i].end());
            bit[i].resize(com[i].size() + 1,0);
//            assert(bit[i].size() == com[i].size() + 1);
//            std::cerr << "prepare " << i << " " << com[i].size() << newl;
        }
//        std::cerr << "ERM\n";
//        std::cerr << "ERM\n";
//        std::cerr << "ERM\n";
//        std::cerr << "ERM\n";
//        std::cerr << "ERM\n";
//        std::cerr << "ERM\n";
//        std::cerr << "ERM\n";
//        std::cerr << "ERM\n";
    }
    int get(int x,int y){
        return std::upper_bound(com[x].begin(),com[x].end(),y) - com[x].begin();
    }
    void update(int x,int y,int v){
//        std::cerr << "bit2d update " << x << " " << y << " " << v << newl;
        for(int i = x;i < (int)bit.size();i += (i & (-i))){
            for(int j = get(i,y);j < (int)bit[i].size();j += (j & (-j))){
//                std::cerr << i << " " << j << newl;
                bit[i][j] += v;
            }
        }
    }
    int sum(int x,int y){
//        std::cerr << "2D BIT SUM" << " " << x << " " << y << newl;
//        if(x < 0){
//            return 0;
//        }
        int ans = 0;
        for(int i = x;i > 0;i -= (i & (-i))){
            for(int j = get(i,y);j > 0;j -= (j & (-j))){
                ans += bit[i][j];
//                assert(i < (int)bit.size());
//                assert(j < (int)bit[i].size());
//                if(j >= (int)bit[i].size()){
//
//                }
//                std::cerr << "CMP " << bit[i].size() << " " << com[i].size() << newl;
//                assert(bit[i].size() == com[i].size() + 1);
            }
        }
        return ans;
    }
    int query(int x1,int y1,int x2,int y2){
//        std::cerr << "QUERY " << x1 << " " << y1 << " " << x2 << " "<< y2 << newl;
        return sum(x2,y2) - sum(x1 - 1,y2) - sum(x2,y1 - 1) + sum(x1 - 1,y1 - 1);
    }
};
struct Event{
    int type,x,idx;
    Event(int type,int x,int idx) : type(type),x(x),idx(idx){

    }
    bool operator < (const Event &other) const {
        return (x < other.x || (x == other.x && type < other.type));
    }
};
std::vector<Event> event;
std::vector<int> com;
std::map<std::map<int,int>,int> m;

int n,k,q,x[N + 1],t[N + 1],a[N + 1],b[N + 1],l[N + 1],y[N + 1],ans[N + 1];

void readData(){
    std::cin >> n >> k >> q;
    for(int i = 1;i <= n;++i){
        std::cin >> x[i] >> t[i] >> a[i] >> b[i];
    }
    for(int i = 1;i <= q;++i){
        std::cin >> l[i] >> y[i];
    }
}
void precompute(){
    for(int i = 1;i <= n;++i){
        event.emplace_back(1,a[i],i);
        event.emplace_back(3,b[i],i);
    }
    for(int i = 1;i <= q;++i){
        event.emplace_back(2,y[i],i);
    }
    std::sort(event.begin(),event.end());
    for(int i = 1;i <= n;++i){
        com.emplace_back(x[i]);
    }
    std::sort(com.begin(),com.end());
    com.erase(std::unique(com.begin(),com.end()),com.end());
//    std::cout << "COM SIZE " << (int)com.size() << newl;
}
int get(int cur_x){
    return std::upper_bound(com.begin(),com.end(),cur_x) - com.begin();
}
void solve(){
//    std::cout << "TEST " << get(9) << newl;
    FenwickTree bit1d(n);
    FenwickTree2D bit2d(n);
    std::map<int,std::map<int,int>> nxt;
    std::map<int,std::map<int,int>> update_queue;
    std::map<int,std::set<int>> pos;
    auto update_precompute = [&](){
        auto fake_add = [&](int idx){
            int comx = get(x[idx]);
            int curt = t[idx];
            ++update_queue[comx][curt];
            if(update_queue[comx][curt] != 1){
                return;
            }
            std::set<int>& curs = pos[curt];
            curs.insert(x[idx]);
//            std::cout << "INSERT " << x[idx] << newl;
            auto it = curs.lower_bound(x[idx]);
//            if(it != curs.begin() && get(*prev(it)) == 0){
//                std::cout << *prev(it) << newl;
//            }
//            if(idx == 4){
//                std::cout << "BRBPATAPIM\n";
//                for(int v : pos[curt]){
//                    std::cout << v << " ";
//                }
//                std::cout << newl;
//            }
            if(it != curs.begin()){
//                std::cout << "FAKE 1 \n";
                bit2d.fake_update(get(*prev(it)),x[idx]);
            }
            if(next(it) != curs.end()){
//                std::cout << "FAKE 2 \n";
//                std::cerr << "IMP " << comx << newl;
                bit2d.fake_update(comx,*next(it));
            }
        };
        auto fake_remov = [&](int idx){
            int comx = get(x[idx]);
            int curt = t[idx];
            --update_queue[comx][curt];
            if(update_queue[comx][curt] > 0){
                return;
            }
            std::set<int>& curs = pos[curt];
            auto it = curs.lower_bound(x[idx]);
            if(next(it) != curs.end() && it != curs.begin()){
//                std::cout << "FAKE 3 \n";
                bit2d.fake_update(get(*prev(it)),*next(it));
            }
            curs.erase(x[idx]);
        };
        for(Event cur : event){
            if(cur.type == 1){
                fake_add(cur.idx);
            }else if(cur.type == 3){
                fake_remov(cur.idx);
            }
        }
        nxt.clear();
        update_queue.clear();
        pos.clear();
    };
    auto add = [&](int idx){
        int comx = get(x[idx]);
        int curt = t[idx];
        ++update_queue[comx][curt];
        if(update_queue[comx][curt] != 1){
            return;
        }
        std::set<int>& curs = pos[curt];
        curs.insert(x[idx]);
        bit1d.update(comx,1);
        auto it = curs.lower_bound(x[idx]);
        if(it != curs.begin()){
            if(next(it) != curs.end()){
                bit2d.update(get(*prev(it)),*next(it),-1);
                bit2d.update(get(*prev(it)),x[idx],1);
                bit2d.update(comx,*next(it),1);
            }else{
                bit2d.update(get(*prev(it)),x[idx],1);
            }
        }else{
            if(next(it) != curs.end()){
                bit2d.update(comx,*next(it),1);
            }
        }
    };
    auto remov = [&](int idx){
        int comx = get(x[idx]);
        int curt = t[idx];
        --update_queue[comx][curt];
        if(update_queue[comx][curt] > 0){
            return;
        }
        bit1d.update(comx,-1);
        std::set<int>& curs = pos[curt];
        auto it = curs.lower_bound(x[idx]);
        if(it != curs.begin()){
            if(next(it) != curs.end()){
                bit2d.update(get(*prev(it)),x[idx],-1);
                bit2d.update(comx,*next(it),-1);
                bit2d.update(get(*prev(it)),*next(it),1);
            }else{
                bit2d.update(get(*prev(it)),x[idx],-1);
            }
        }else{
            if(next(it) != curs.end()){
                bit2d.update(comx,*next(it),-1);
            }
        }
        curs.erase(x[idx]);
    };
    update_precompute();
    bit2d.prepare();
    for(Event cur : event){
        auto f = [&](int l,int r){
            int coml = get(l);
            int comr = get(r);
//            std::cout << l << " " << r << " " << bit2d.query(coml,1,comr,r) << newl;
            return bit1d.query(coml,comr) - bit2d.query(coml,1,comr,r);
        };
        if(cur.type == 1){
            add(cur.idx);
        }else if(cur.type == 3){
            remov(cur.idx);
        }else{
            int lo = 0,hi = 1e8,cur_ans = -1;
            while(lo <= hi){
                int mid = (lo + hi) / 2;
                int ll = std::max(1,l[cur.idx] - mid);
                int rr = std::min((int)1e8,l[cur.idx] + mid);
                if(f(ll,rr) == k){
                    cur_ans = mid;
                    hi = mid - 1;
                }else{
                    lo = mid + 1;
                }
            }
            ans[cur.idx] = cur_ans;
        }
//        std::cout << "IMP " << f(1,n) << newl;
    }
}
void print_answer(){
    for(int i = 1;i <= q;++i){
        std::cout << ans[i] << newl;
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    precompute();
    solve();
    print_answer();
    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
5 10
*/

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