Submission #731904

#	Time	Username	Problem	Language	Result	Execution time	Memory
731904		minhcool	New Home (APIO18_new_home)	C++17	5 / 100	5040 ms	622824 KiB

new_home

#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;
const int mod = 1e9 + 7, oo = 1e9 + 7;

/*
Algo (Ig)
*/

int n, k, q;

int a[N], b[N], x[N], t[N];

int l[N], y[N];

vector<int> times;

vector<ii> opes[1048576];
vector<int> asks[N];
multiset<int> mls[N];

vector<int> mini[1048576], maxi[1048576];

vector<int> ask_pos;

int cal[100000005];

int f(int x){
    if(cal[x] != -1) return cal[x];
    return cal[x] = (lower_bound(ask_pos.begin(), ask_pos.end(), x) - ask_pos.begin());
}

// get position to add/erase
ii get_pos(int l, int r){
    assert(l <= r);
    int temp1 = f(l);
    int temp2 = f(r);
    temp2--;
    if(temp2 < temp1){
    //	cout << "OK\n";
    //	exit(0);
	}
    //assert(temp2 >= temp1);
    return {temp1, temp2};
}

void build(int id, int l, int r){
    mini[id].push_back(oo);
    maxi[id].push_back(-oo);
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

int tol = 0;

int itr = 0;
ii ope[10000005];

int L, R, val, type;

// update the minimum & maximum
void add(int id, int l, int r){
    if(l > R || r < L || l > r) return;
    if(l >= L && r <= R){
        if(!type){
        	if(val >= mini[id].back()) return;
            mini[id].emplace_back(min(mini[id].back(), val));
            itr++;
            ope[itr] = {id, 0};
//            opes.pb({id, 0});
        }
        else{
        	if(val <= maxi[id].back()) return;
            itr++;
            ope[itr] = {id, 1};
            maxi[id].emplace_back(max(maxi[id].back(), val));
        }
        tol++;
        return;
    }
    int mid = (l + r) >> 1;
    add(id << 1, l, mid);
    add(id << 1 | 1, mid + 1, r);
}

void addd(int id, int l, int r, int _L, int _R, int _val, int _type){
	L = _L, R = _R, val = _val, type = _type;
	add(id, l, r);
}

// erase the lasest changes

void er(int id, int l, int r, int L, int R, int type){
    if(l > R || r < L || l > r) return;
    if(l >= L && r <= R){
        if(!type){
//            assert(mini[id].size());
            mini[id].pop_back();
        }
        else{
  //          assert(maxi[id].size());
            maxi[id].pop_back();
        }
        return;
    }
    int mid = (l + r) >> 1;
    er(id << 1, l, mid, L, R, type);
    er(id << 1 | 1, mid + 1, r, L, R, type);
}

int answer[N];

ii ans_que = {oo, -oo};

// easy query stuff

void que(int id, int l, int r, int pos){
    ans_que.fi = min(ans_que.fi, mini[id].back());
    ans_que.se = max(ans_que.se, maxi[id].back());
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid) que(id << 1, l, mid, pos);
    else que(id << 1 | 1, mid + 1, r, pos);
}

// for persistent segment tree

void upd(int id, int l, int r, int L, int R, ii v){
    if(l > R || r < L) return;
    if(l >= L && r <= R){
        opes[id].pb(v);
        return;
    }
    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, L, R, v);
    upd(id << 1 | 1, mid + 1, r, L, R, v);
}

map<ii, int> answ;// b/c i'm lazy

//ii opes[000005];

void trav(int id, int l, int r){
    //cout << id << " " << l << " " << r << "\n";
    tol = 0;
    for(auto it : opes[id]){
       // cout << id << " " << l << " " << r << " " << it.fi << " " << it.se << "\n";
        multiset<int>::iterator itt = mls[it.se].lower_bound(it.fi), itt2 = itt, itt3;
  //       if(itt == mls[it.se].end()) exit(0);
    //    assert(itt != mls[it.se].end());
        itt2++;
        bool ck1 = (itt == mls[it.se].begin()), ck2 = (itt2 == mls[it.se].end());
        if(ck1 && ck2){// everything turns into -oo and oo
            addd(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, -oo, 0);
            addd(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, oo, 1);
            mls[it.se].erase(itt);
            continue;
        }
        else if(ck1){// the left side is missing
            int pos = f((*itt2));
            pos--;
            if(pos) addd(1, 1, ask_pos.size() - 1, 1, pos, (*itt2), 1);
        }
        else if(ck2){// the right side is missing
            itt2--;
            itt2--;
            int pos = f((*itt2));
            if(pos < ask_pos.size()) addd(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, (*itt2), 0);
        }
        else{
            itt2 = itt3 = itt;
            itt2++; itt3--;
            int md = ((*itt2) + (*itt3)) / 2;
            /*
            int pos1 = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt3)) - ask_pos.begin();
            int pos2 = upper_bound(ask_pos.begin(), ask_pos.end(), md) - ask_pos.begin();
            int pos3 = upper_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();*/
            int pos1 = f((*itt3)), pos2 = f(md + 1), pos3 = f((*itt2) + 1);
            pos2--;
            pos3--;
            if(pos1 <= pos2) addd(1, 1, ask_pos.size() - 1, pos1, pos2, (*itt3), 0);
            if(pos2 < pos3) addd(1, 1, ask_pos.size() - 1, pos2 + 1, pos3, (*itt2), 1);
        }
        mls[it.se].erase(itt);
    }
    int temp = tol;
    if(l == r){
        for(auto it : asks[l]){
            ans_que = {oo, -oo};
            int temp = lower_bound(ask_pos.begin(), ask_pos.end(), it) - ask_pos.begin();
            que(1, 1, ask_pos.size() - 1, temp);
            answ[{times[l], it}] = max(it - ans_que.fi, ans_que.se - it);
        }
    }
    else{
        int mid = (l + r) >> 1;
        trav(id << 1, l, mid);
        trav(id << 1 | 1, mid + 1, r);
    }
    //reverse(opes[id].begin(), opes[id].end());
    for(auto it : opes[id]){
        mls[it.se].insert(it.fi);
        /*
        multiset<int>::iterator itt = mls[it.se].lower_bound(it.fi), itt2 = itt, itt3;
        assert(itt != mls[it.se].end());
        itt2++;
        bool ck1 = (itt == mls[it.se].begin()), ck2 = (itt2 == mls[it.se].end());
        if(ck1 && ck2){
            er(1, 1, ask_pos.size() - 1,  1, ask_pos.size() - 1, 0);
            er(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, 1);
            continue;
        }
        else if(ck1){
            int pos = f((*itt2));
            pos--;
            if(pos) er(1, 1, ask_pos.size() - 1, 1, pos, 1);
        }
        else if(ck2){
            itt2--;
            itt2--;
            int pos = f((*itt2));
            //int pos = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
            if(pos < ask_pos.size()) er(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, 0);
        }
        else{
            itt2 = itt3 = itt;
            itt2++; itt3--;
            int md = ((*itt2) + (*itt3)) / 2;
            int pos1 = f((*itt3)), pos2 = f(md + 1), pos3 = f((*itt2) + 1);
            pos2--;
            pos3--;
            if(pos1 <= pos2) er(1, 1, ask_pos.size() - 1, pos1, pos2, 0);
            if(pos2 < pos3) er(1, 1, ask_pos.size() - 1, pos2 + 1, pos3, 1);
        }*/
        //mls[it.se].insert(it.fi);
    }
    for(int i = 1; i <= temp; i++){
        int type = ope[itr].se, id = ope[itr].fi;
        if(!type) mini[id].pop_back();
        else maxi[id].pop_back();
        itr--;
    }
}

void process(){
    for(int i = 0; i <= 100000000; i++) cal[i] = -1;
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++) cin >> x[i] >> t[i] >> a[i] >> b[i];
    for(int i = 1; i <= q; i++){
        cin >> l[i] >> y[i];
        ask_pos.pb(l[i]);
    }
    times.pb(0);
    times.pb(1);
    times.pb(1e8);
    /*
    for(int i = 1; i <= n; i++){
        if(a[i] > 2) times.pb(a[i] - 1);
        if((b[i] + 1) < 1e8) times.pb(b[i] + 1);
    }*/
    ask_pos.pb(0);
    sort(ask_pos.begin(), ask_pos.end());
    ask_pos.resize(unique(ask_pos.begin(), ask_pos.end()) - ask_pos.begin());
    // push the erase operations
    for(int i = 1; i <= q; i++) times.pb(y[i]);
    sort(times.begin(), times.end());
    times.resize(unique(times.begin(), times.end()) - times.begin());
    for(int i = 1; i <= n; i++){
        if(a[i] > 1){
            int le = 1, ri = lower_bound(times.begin(), times.end(), a[i]) - times.begin();
            ri--;
            if(le <= ri) upd(1, 1, times.size() - 1, le, ri, {x[i], t[i]});
        }
        if((b[i] + 1 < 1e8)){
            int le = lower_bound(times.begin(), times.end(), b[i] + 1) - times.begin(), ri = times.size() - 1;
            upd(1, 1, times.size() - 1, le, ri, {x[i], t[i]});
        }
    }
    //exit(0);
    // insert the queries
    for(int i = 1; i <= q; i++){
        int temp = lower_bound(times.begin(), times.end(), y[i]) - times.begin();
        asks[temp].pb(l[i]);
    }
    // initialize (not erase anything)
    for(int i = 1; i <= n; i++) mls[t[i]].insert(x[i]);
   // cout << ask_pos.size() - 1 << "\n";
//    exit(0);
    build(1, 1, ask_pos.size() - 1);
    for(int i = 1; i <= k; i++){
        if(!mls[i].size()){
            addd(1, 1, ask_pos.size() - 1,  1, ask_pos.size() - 1, -oo, 0);
            addd(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, oo, 1);
            continue;
        }
        //continue;
        int lst = -oo;
        int cnt = 0;
        for(multiset<int>::iterator it = mls[i].begin(); it != mls[i].end(); it++){
            int le = 1, ri = 1e8;
            if(it != mls[i].begin()){
                multiset<int>::iterator it2 = it;
                it2--;
                le = ((*it) + (*it2)) / 2 + 1;
            }
            multiset<int>::iterator it2 = it;
            it2++;
            if(it2 != mls[i].end()) ri = ((*it) + (*it2)) / 2;
 //           if(le > ri || le == ask_pos.size()) continue;
            if(le > ri) continue;
            if(le > ask_pos.back()) continue;
            ii temp = get_pos(le, ri);
            if(temp.fi > temp.se) continue;
            temp.se = min(temp.se, (int)ask_pos.size() - 1);
            if(temp.fi > temp.se) continue;
            int posi = f(*it);
            if(temp.fi < posi) addd(1, 1, ask_pos.size() - 1, temp.fi, posi - 1, (*it), 1);
            if(posi <= temp.se) addd(1, 1, ask_pos.size() - 1, posi, temp.se, (*it), 0);
        }
    }
    //exit(0);
    trav(1, 1, times.size() - 1);
    //cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
    for(int i = 1; i <= q; i++) cout << (answ[{y[i], l[i]}] <= 1e8 ? answ[{y[i], l[i]}] : -1) << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
//    freopen("test_input.txt", "r", stdin);
//    freopen("test_output.txt", "w", stdout);
    cin.tie(0);
    process();
}

Compilation message (stderr)

new_home.cpp: In function 'void trav(int, int, int)':
new_home.cpp:180:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |             if(pos < ask_pos.size()) addd(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, (*itt2), 0);
      |                ~~~~^~~~~~~~~~~~~~~~
new_home.cpp: In function 'void process()':
new_home.cpp:309:13: warning: unused variable 'lst' [-Wunused-variable]
  309 |         int lst = -oo;
      |             ^~~
new_home.cpp:310:13: warning: unused variable 'cnt' [-Wunused-variable]
  310 |         int cnt = 0;
      |             ^~~

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