oj.uz

Submission #365339

# Submission time Handle Problem Language Result Execution time Memory
365339 2021-02-11T13:36:31 Z doowey New Home (APIO18_new_home) C++14
12 / 100
 5000 ms 699364 KB 
#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;
    auto pv = it;
    pv -- ;
    nx ++ ;
    cum = (*it) + (*nx);
    if(cum % 2 == 0){
        bb.push_back(cum/2);
    }
    else{
        bb.push_back(cum/2);
        bb.push_back(cum/2+1);
    }
    cum = (*pv) + (*it);
    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()){
        pv -- ;
        cum = (*pv + *nx);
        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 ++ ;
                pv -- ;
                add_f(*pv, *nx, 1);
                add_f(*it, *nx, 0);
                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 ++ ;
                pv--;
                add_f(*it, *nx, 1);
                add_f(*pv, *it, 1);
                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;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:176: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]
  176 |         while(iq < eve.size() && eve[iq].fi <= p.fi){
      |               ~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 465388 KB Output is correct
2 Correct 296 ms 465388 KB Output is correct
3 Correct 299 ms 465388 KB Output is correct
4 Correct 293 ms 465388 KB Output is correct
5 Correct 303 ms 465516 KB Output is correct
6 Correct 296 ms 465644 KB Output is correct
7 Correct 301 ms 465772 KB Output is correct
8 Correct 303 ms 465772 KB Output is correct
9 Correct 299 ms 466028 KB Output is correct
10 Correct 330 ms 465920 KB Output is correct
11 Correct 301 ms 465516 KB Output is correct
12 Correct 301 ms 465516 KB Output is correct
13 Correct 294 ms 465388 KB Output is correct
14 Correct 304 ms 465516 KB Output is correct
15 Correct 300 ms 465772 KB Output is correct
16 Correct 304 ms 465772 KB Output is correct
17 Correct 329 ms 465516 KB Output is correct
18 Correct 300 ms 465660 KB Output is correct
19 Correct 319 ms 465772 KB Output is correct
20 Correct 301 ms 465644 KB Output is correct
21 Correct 301 ms 465644 KB Output is correct
22 Correct 306 ms 466028 KB Output is correct
23 Correct 319 ms 465900 KB Output is correct
24 Correct 298 ms 465772 KB Output is correct
25 Correct 299 ms 465616 KB Output is correct
26 Correct 299 ms 465516 KB Output is correct
27 Correct 298 ms 465516 KB Output is correct
28 Correct 319 ms 465516 KB Output is correct
29 Correct 308 ms 465516 KB Output is correct
30 Correct 300 ms 465516 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 465388 KB Output is correct
2 Correct 296 ms 465388 KB Output is correct
3 Correct 299 ms 465388 KB Output is correct
4 Correct 293 ms 465388 KB Output is correct
5 Correct 303 ms 465516 KB Output is correct
6 Correct 296 ms 465644 KB Output is correct
7 Correct 301 ms 465772 KB Output is correct
8 Correct 303 ms 465772 KB Output is correct
9 Correct 299 ms 466028 KB Output is correct
10 Correct 330 ms 465920 KB Output is correct
11 Correct 301 ms 465516 KB Output is correct
12 Correct 301 ms 465516 KB Output is correct
13 Correct 294 ms 465388 KB Output is correct
14 Correct 304 ms 465516 KB Output is correct
15 Correct 300 ms 465772 KB Output is correct
16 Correct 304 ms 465772 KB Output is correct
17 Correct 329 ms 465516 KB Output is correct
18 Correct 300 ms 465660 KB Output is correct
19 Correct 319 ms 465772 KB Output is correct
20 Correct 301 ms 465644 KB Output is correct
21 Correct 301 ms 465644 KB Output is correct
22 Correct 306 ms 466028 KB Output is correct
23 Correct 319 ms 465900 KB Output is correct
24 Correct 298 ms 465772 KB Output is correct
25 Correct 299 ms 465616 KB Output is correct
26 Correct 299 ms 465516 KB Output is correct
27 Correct 298 ms 465516 KB Output is correct
28 Correct 319 ms 465516 KB Output is correct
29 Correct 308 ms 465516 KB Output is correct
30 Correct 300 ms 465516 KB Output is correct
31 Correct 3945 ms 529872 KB Output is correct
32 Correct 594 ms 474708 KB Output is correct
33 Correct 2063 ms 486404 KB Output is correct
34 Correct 4067 ms 497256 KB Output is correct
35 Correct 3248 ms 521108 KB Output is correct
36 Correct 1979 ms 502284 KB Output is correct
37 Correct 1869 ms 476464 KB Output is correct
38 Correct 1351 ms 475264 KB Output is correct
39 Correct 1050 ms 473844 KB Output is correct
40 Correct 1085 ms 473860 KB Output is correct
41 Correct 2478 ms 474596 KB Output is correct
42 Correct 2625 ms 474760 KB Output is correct
43 Correct 461 ms 481120 KB Output is correct
44 Correct 2350 ms 474228 KB Output is correct
45 Correct 1990 ms 474084 KB Output is correct
46 Correct 1616 ms 473832 KB Output is correct
47 Correct 1085 ms 473444 KB Output is correct
48 Correct 1010 ms 473512 KB Output is correct
49 Correct 1269 ms 473736 KB Output is correct
50 Correct 1771 ms 474100 KB Output is correct
51 Correct 1299 ms 473584 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 465388 KB Output is correct
2 Correct 296 ms 465388 KB Output is correct
3 Correct 299 ms 465388 KB Output is correct
4 Correct 293 ms 465388 KB Output is correct
5 Correct 303 ms 465516 KB Output is correct
6 Correct 296 ms 465644 KB Output is correct
7 Correct 301 ms 465772 KB Output is correct
8 Correct 303 ms 465772 KB Output is correct
9 Correct 299 ms 466028 KB Output is correct
10 Correct 330 ms 465920 KB Output is correct
11 Correct 301 ms 465516 KB Output is correct
12 Correct 301 ms 465516 KB Output is correct
13 Correct 294 ms 465388 KB Output is correct
14 Correct 304 ms 465516 KB Output is correct
15 Correct 300 ms 465772 KB Output is correct
16 Correct 304 ms 465772 KB Output is correct
17 Correct 329 ms 465516 KB Output is correct
18 Correct 300 ms 465660 KB Output is correct
19 Correct 319 ms 465772 KB Output is correct
20 Correct 301 ms 465644 KB Output is correct
21 Correct 301 ms 465644 KB Output is correct
22 Correct 306 ms 466028 KB Output is correct
23 Correct 319 ms 465900 KB Output is correct
24 Correct 298 ms 465772 KB Output is correct
25 Correct 299 ms 465616 KB Output is correct
26 Correct 299 ms 465516 KB Output is correct
27 Correct 298 ms 465516 KB Output is correct
28 Correct 319 ms 465516 KB Output is correct
29 Correct 308 ms 465516 KB Output is correct
30 Correct 300 ms 465516 KB Output is correct
31 Correct 3945 ms 529872 KB Output is correct
32 Correct 594 ms 474708 KB Output is correct
33 Correct 2063 ms 486404 KB Output is correct
34 Correct 4067 ms 497256 KB Output is correct
35 Correct 3248 ms 521108 KB Output is correct
36 Correct 1979 ms 502284 KB Output is correct
37 Correct 1869 ms 476464 KB Output is correct
38 Correct 1351 ms 475264 KB Output is correct
39 Correct 1050 ms 473844 KB Output is correct
40 Correct 1085 ms 473860 KB Output is correct
41 Correct 2478 ms 474596 KB Output is correct
42 Correct 2625 ms 474760 KB Output is correct
43 Correct 461 ms 481120 KB Output is correct
44 Correct 2350 ms 474228 KB Output is correct
45 Correct 1990 ms 474084 KB Output is correct
46 Correct 1616 ms 473832 KB Output is correct
47 Correct 1085 ms 473444 KB Output is correct
48 Correct 1010 ms 473512 KB Output is correct
49 Correct 1269 ms 473736 KB Output is correct
50 Correct 1771 ms 474100 KB Output is correct
51 Correct 1299 ms 473584 KB Output is correct
52 Correct 3688 ms 622052 KB Output is correct
53 Correct 3929 ms 532072 KB Output is correct
54 Execution timed out 5134 ms 575192 KB Time limit exceeded
55 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 465388 KB Output is correct
2 Correct 296 ms 465388 KB Output is correct
3 Correct 299 ms 465388 KB Output is correct
4 Correct 293 ms 465388 KB Output is correct
5 Correct 303 ms 465516 KB Output is correct
6 Correct 296 ms 465644 KB Output is correct
7 Correct 301 ms 465772 KB Output is correct
8 Correct 303 ms 465772 KB Output is correct
9 Correct 299 ms 466028 KB Output is correct
10 Correct 330 ms 465920 KB Output is correct
11 Correct 301 ms 465516 KB Output is correct
12 Correct 301 ms 465516 KB Output is correct
13 Correct 294 ms 465388 KB Output is correct
14 Correct 304 ms 465516 KB Output is correct
15 Correct 300 ms 465772 KB Output is correct
16 Correct 304 ms 465772 KB Output is correct
17 Correct 329 ms 465516 KB Output is correct
18 Correct 300 ms 465660 KB Output is correct
19 Correct 319 ms 465772 KB Output is correct
20 Correct 301 ms 465644 KB Output is correct
21 Correct 301 ms 465644 KB Output is correct
22 Correct 306 ms 466028 KB Output is correct
23 Correct 319 ms 465900 KB Output is correct
24 Correct 298 ms 465772 KB Output is correct
25 Correct 299 ms 465616 KB Output is correct
26 Correct 299 ms 465516 KB Output is correct
27 Correct 298 ms 465516 KB Output is correct
28 Correct 319 ms 465516 KB Output is correct
29 Correct 308 ms 465516 KB Output is correct
30 Correct 300 ms 465516 KB Output is correct
31 Correct 3945 ms 529872 KB Output is correct
32 Correct 594 ms 474708 KB Output is correct
33 Correct 2063 ms 486404 KB Output is correct
34 Correct 4067 ms 497256 KB Output is correct
35 Correct 3248 ms 521108 KB Output is correct
36 Correct 1979 ms 502284 KB Output is correct
37 Correct 1869 ms 476464 KB Output is correct
38 Correct 1351 ms 475264 KB Output is correct
39 Correct 1050 ms 473844 KB Output is correct
40 Correct 1085 ms 473860 KB Output is correct
41 Correct 2478 ms 474596 KB Output is correct
42 Correct 2625 ms 474760 KB Output is correct
43 Correct 461 ms 481120 KB Output is correct
44 Correct 2350 ms 474228 KB Output is correct
45 Correct 1990 ms 474084 KB Output is correct
46 Correct 1616 ms 473832 KB Output is correct
47 Correct 1085 ms 473444 KB Output is correct
48 Correct 1010 ms 473512 KB Output is correct
49 Correct 1269 ms 473736 KB Output is correct
50 Correct 1771 ms 474100 KB Output is correct
51 Correct 1299 ms 473584 KB Output is correct
52 Execution timed out 5101 ms 699364 KB Time limit exceeded
53 Halted 0 ms 0 KB -