oj.uz

Submission #731912

# Submission time Handle Problem Language Result Execution time Memory
731912 2023-04-28T06:45:16 Z minhcool New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 710080 KB 
#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) 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 486684 KB Output is correct
2 Correct 199 ms 486644 KB Output is correct
3 Correct 217 ms 486756 KB Output is correct
4 Correct 228 ms 486732 KB Output is correct
5 Correct 200 ms 486836 KB Output is correct
6 Correct 201 ms 486976 KB Output is correct
7 Correct 217 ms 487088 KB Output is correct
8 Correct 208 ms 487000 KB Output is correct
9 Correct 200 ms 487048 KB Output is correct
10 Correct 216 ms 486976 KB Output is correct
11 Correct 207 ms 487012 KB Output is correct
12 Correct 211 ms 486936 KB Output is correct
13 Correct 228 ms 486896 KB Output is correct
14 Correct 237 ms 486972 KB Output is correct
15 Correct 205 ms 486912 KB Output is correct
16 Correct 233 ms 486884 KB Output is correct
17 Correct 227 ms 487016 KB Output is correct
18 Correct 223 ms 486992 KB Output is correct
19 Correct 200 ms 486980 KB Output is correct
20 Correct 195 ms 486988 KB Output is correct
21 Correct 202 ms 486728 KB Output is correct
22 Correct 191 ms 486908 KB Output is correct
23 Correct 188 ms 486988 KB Output is correct
24 Correct 205 ms 487008 KB Output is correct
25 Correct 204 ms 487092 KB Output is correct
26 Correct 199 ms 486884 KB Output is correct
27 Correct 199 ms 486788 KB Output is correct
28 Correct 210 ms 486976 KB Output is correct
29 Correct 206 ms 486968 KB Output is correct
30 Correct 194 ms 486884 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 486684 KB Output is correct
2 Correct 199 ms 486644 KB Output is correct
3 Correct 217 ms 486756 KB Output is correct
4 Correct 228 ms 486732 KB Output is correct
5 Correct 200 ms 486836 KB Output is correct
6 Correct 201 ms 486976 KB Output is correct
7 Correct 217 ms 487088 KB Output is correct
8 Correct 208 ms 487000 KB Output is correct
9 Correct 200 ms 487048 KB Output is correct
10 Correct 216 ms 486976 KB Output is correct
11 Correct 207 ms 487012 KB Output is correct
12 Correct 211 ms 486936 KB Output is correct
13 Correct 228 ms 486896 KB Output is correct
14 Correct 237 ms 486972 KB Output is correct
15 Correct 205 ms 486912 KB Output is correct
16 Correct 233 ms 486884 KB Output is correct
17 Correct 227 ms 487016 KB Output is correct
18 Correct 223 ms 486992 KB Output is correct
19 Correct 200 ms 486980 KB Output is correct
20 Correct 195 ms 486988 KB Output is correct
21 Correct 202 ms 486728 KB Output is correct
22 Correct 191 ms 486908 KB Output is correct
23 Correct 188 ms 486988 KB Output is correct
24 Correct 205 ms 487008 KB Output is correct
25 Correct 204 ms 487092 KB Output is correct
26 Correct 199 ms 486884 KB Output is correct
27 Correct 199 ms 486788 KB Output is correct
28 Correct 210 ms 486976 KB Output is correct
29 Correct 206 ms 486968 KB Output is correct
30 Correct 194 ms 486884 KB Output is correct
31 Correct 2468 ms 541216 KB Output is correct
32 Correct 378 ms 495312 KB Output is correct
33 Correct 2109 ms 526816 KB Output is correct
34 Correct 2738 ms 542336 KB Output is correct
35 Correct 2587 ms 536452 KB Output is correct
36 Correct 2372 ms 525932 KB Output is correct
37 Correct 1940 ms 530464 KB Output is correct
38 Incorrect 1564 ms 523360 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2723 ms 678052 KB Output is correct
2 Incorrect 1852 ms 589844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5058 ms 710080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 486684 KB Output is correct
2 Correct 199 ms 486644 KB Output is correct
3 Correct 217 ms 486756 KB Output is correct
4 Correct 228 ms 486732 KB Output is correct
5 Correct 200 ms 486836 KB Output is correct
6 Correct 201 ms 486976 KB Output is correct
7 Correct 217 ms 487088 KB Output is correct
8 Correct 208 ms 487000 KB Output is correct
9 Correct 200 ms 487048 KB Output is correct
10 Correct 216 ms 486976 KB Output is correct
11 Correct 207 ms 487012 KB Output is correct
12 Correct 211 ms 486936 KB Output is correct
13 Correct 228 ms 486896 KB Output is correct
14 Correct 237 ms 486972 KB Output is correct
15 Correct 205 ms 486912 KB Output is correct
16 Correct 233 ms 486884 KB Output is correct
17 Correct 227 ms 487016 KB Output is correct
18 Correct 223 ms 486992 KB Output is correct
19 Correct 200 ms 486980 KB Output is correct
20 Correct 195 ms 486988 KB Output is correct
21 Correct 202 ms 486728 KB Output is correct
22 Correct 191 ms 486908 KB Output is correct
23 Correct 188 ms 486988 KB Output is correct
24 Correct 205 ms 487008 KB Output is correct
25 Correct 204 ms 487092 KB Output is correct
26 Correct 199 ms 486884 KB Output is correct
27 Correct 199 ms 486788 KB Output is correct
28 Correct 210 ms 486976 KB Output is correct
29 Correct 206 ms 486968 KB Output is correct
30 Correct 194 ms 486884 KB Output is correct
31 Correct 2468 ms 541216 KB Output is correct
32 Correct 378 ms 495312 KB Output is correct
33 Correct 2109 ms 526816 KB Output is correct
34 Correct 2738 ms 542336 KB Output is correct
35 Correct 2587 ms 536452 KB Output is correct
36 Correct 2372 ms 525932 KB Output is correct
37 Correct 1940 ms 530464 KB Output is correct
38 Incorrect 1564 ms 523360 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 486684 KB Output is correct
2 Correct 199 ms 486644 KB Output is correct
3 Correct 217 ms 486756 KB Output is correct
4 Correct 228 ms 486732 KB Output is correct
5 Correct 200 ms 486836 KB Output is correct
6 Correct 201 ms 486976 KB Output is correct
7 Correct 217 ms 487088 KB Output is correct
8 Correct 208 ms 487000 KB Output is correct
9 Correct 200 ms 487048 KB Output is correct
10 Correct 216 ms 486976 KB Output is correct
11 Correct 207 ms 487012 KB Output is correct
12 Correct 211 ms 486936 KB Output is correct
13 Correct 228 ms 486896 KB Output is correct
14 Correct 237 ms 486972 KB Output is correct
15 Correct 205 ms 486912 KB Output is correct
16 Correct 233 ms 486884 KB Output is correct
17 Correct 227 ms 487016 KB Output is correct
18 Correct 223 ms 486992 KB Output is correct
19 Correct 200 ms 486980 KB Output is correct
20 Correct 195 ms 486988 KB Output is correct
21 Correct 202 ms 486728 KB Output is correct
22 Correct 191 ms 486908 KB Output is correct
23 Correct 188 ms 486988 KB Output is correct
24 Correct 205 ms 487008 KB Output is correct
25 Correct 204 ms 487092 KB Output is correct
26 Correct 199 ms 486884 KB Output is correct
27 Correct 199 ms 486788 KB Output is correct
28 Correct 210 ms 486976 KB Output is correct
29 Correct 206 ms 486968 KB Output is correct
30 Correct 194 ms 486884 KB Output is correct
31 Correct 2468 ms 541216 KB Output is correct
32 Correct 378 ms 495312 KB Output is correct
33 Correct 2109 ms 526816 KB Output is correct
34 Correct 2738 ms 542336 KB Output is correct
35 Correct 2587 ms 536452 KB Output is correct
36 Correct 2372 ms 525932 KB Output is correct
37 Correct 1940 ms 530464 KB Output is correct
38 Incorrect 1564 ms 523360 KB Output isn't correct
39 Halted 0 ms 0 KB -