oj.uz

Submission #365503

# Submission time Handle Problem Language Result Execution time Memory
365503 2021-02-11T18:35:54 Z doowey New Home (APIO18_new_home) C++14
100 / 100
 3500 ms 381344 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 + 5;
const int inf = (int)1e9;
map<int, int> cnt[N];
int x[N], t[N], a[N], b[N];

vector<int> cors;

struct lin{
    int tim;
    int lef;
    int rig;
    int mode;
};

int cur;

vector<lin> lis;


const int M = (int)2e6 + 10;
map<int, int> low[M];
map<int, int> high[M];

int segt[M * 2][2];
int m;

int getid(int pp){
    return lower_bound(cors.begin(), cors.end(), pp) - cors.begin();
}

void segm(int li, int ri, int mod){
    lis.push_back({cur, li, ri, mod});
    cors.push_back((li + ri) / 2);
}

void setv(int id, int q, int vl){
    id += m;
    segt[id][q] = vl;
    id /= 2;
    while(id > 0){
        if(q == 0) segt[id][q] = max(segt[id*2][q], segt[id*2+1][q]);
        else segt[id][q] = min(segt[id*2][q], segt[id*2+1][q]);
        id /= 2;
    }
}

int get(int li, int ri, int q){
    li += m;
    ri += m;
    int ret = 0;
    if(q == 0) ret = -inf;
    else ret = inf;
    while(li <= ri){
        if(li % 2 == 1){
            if(q == 0) ret = max(ret, segt[li][0]);
            else ret = min(ret, segt[li][1]);
            li ++ ;
        }
        if(ri % 2 == 0){
            if(q == 0) ret = max(ret, segt[ri][0]);
            else ret = min(ret, segt[ri][1]);
            ri -- ;
        }
        li /= 2;
        ri /= 2;
    }
    return ret;
}

int fin_p(int pp){
    int ix = getid(pp);
    return max(pp - get(ix, m - 1, 1), get(0, ix, 0) - pp);
}

void add_line(lin nw){
    int li = nw.lef;
    int ri = nw.rig;
    int vv = nw.mode;
    int mid = (li + ri) / 2;
    int mi = getid(mid);
    if(nw.mode == 0){
        low[mi][li] ++ ;
        high[mi][ri] ++ ;
    }
    else{
        low[mi][li] -- ;
        if(low[mi][li] == 0)
            low[mi].erase(li);
        high[mi][ri] -- ;
        if(high[mi][ri] == 0)
            high[mi].erase(ri);
    }
    int lw = inf;
    int rw = -inf;
    if(!low[mi].empty()){
        auto it = low[mi].begin();
        lw = min(lw, it->fi);
    }
    if(!high[mi].empty()){
        auto it = high[mi].end();
        it -- ;
        rw = max(rw, it->fi);
    }
    setv(mi, 1, lw);
    setv(mi, 0, rw);
}

void add(int typ, int v){
    cnt[typ][v] ++ ;
    auto it = cnt[typ].find(v);
    auto nx = it;
    auto pv = it;
    if(cnt[typ][v] == 1){
        nx ++ ;
    }
    pv -- ;
    segm(pv->fi, nx->fi, 1);
    segm(pv->fi, it->fi, 0);
    segm(it->fi, nx->fi, 0);
}

void del(int typ, int v){
    auto it = cnt[typ].find(v);
    auto nx = it;
    auto pv = it;
    if(cnt[typ][v] == 1){
        nx ++ ;
    }
    pv -- ;

    segm(pv->fi, it->fi, 1);
    segm(it->fi, nx->fi, 1);
    segm(pv->fi, nx->fi, 0);
    cnt[typ][v] -- ;
    if(cnt[typ][v] == 0){
        cnt[typ].erase(v);
    }
}

int xx[N];
int yr[N];

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];
        x[i] *= 2;
        cors.push_back(x[i]);
        eve.push_back(mp(a[i], i));
        eve.push_back(mp(b[i] + 1, i));
    }
    vector<pii> ord;
    for(int i = 1; i <= q; i ++ ){
        cin >> xx[i] >> yr[i];
        xx[i] *= 2;
        cors.push_back(xx[i]);
        ord.push_back(mp(yr[i], i));
    }
    sort(ord.begin(), ord.end());
    sort(eve.begin(), eve.end());
    for(int i = 1; i <= k ; i ++ ){
        cnt[i][-inf] ++ ;
        cnt[i][inf] ++ ;
        segm(-inf, inf, 0);
    }
    for(int i = 0 ; i < eve.size(); i ++ ){
        cur = eve[i].fi;
        if(cur == a[eve[i].se]){
            add(t[eve[i].se], x[eve[i].se]);
        }
        else{
            del(t[eve[i].se], x[eve[i].se]);
        }
    }
    sort(cors.begin(), cors.end());
    cors.resize(unique(cors.begin(), cors.end()) - cors.begin());
    m = cors.size();
    for(int i = 0 ; i < m * 2; i ++ ){
        segt[i][0]=-inf;
        segt[i][1]=inf;
    }
    int it = 0;
    int vv;
    for(auto e : ord){
        while(it < lis.size() && lis[it].tim <= e.fi){
            add_line(lis[it]);
            it ++ ;
        }
        vv = fin_p(xx[e.se]);
        vv /= 2;
        if(vv > (int)1e8)
            soln[e.se] = -1;
        else
            soln[e.se] = vv;
    }
    for(int i = 1; i <= q; i ++ ){
        cout << soln[i] << "\n";
    }
    return 0;
}

Compilation message

new_home.cpp: In function 'void add_line(lin)':
new_home.cpp:90:9: warning: unused variable 'vv' [-Wunused-variable]
   90 |     int vv = nw.mode;
      |         ^~
new_home.cpp: In function 'int main()':
new_home.cpp:183:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     for(int i = 0 ; i < eve.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
new_home.cpp:202:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<lin>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |         while(it < lis.size() && lis[it].tim <= e.fi){
      |               ~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 202348 KB Output is correct
2 Correct 124 ms 202348 KB Output is correct
3 Correct 123 ms 202348 KB Output is correct
4 Correct 121 ms 202348 KB Output is correct
5 Correct 130 ms 202468 KB Output is correct
6 Correct 124 ms 202624 KB Output is correct
7 Correct 123 ms 202604 KB Output is correct
8 Correct 122 ms 202476 KB Output is correct
9 Correct 123 ms 202604 KB Output is correct
10 Correct 123 ms 202476 KB Output is correct
11 Correct 124 ms 202604 KB Output is correct
12 Correct 123 ms 202476 KB Output is correct
13 Correct 124 ms 202496 KB Output is correct
14 Correct 124 ms 202732 KB Output is correct
15 Correct 126 ms 202604 KB Output is correct
16 Correct 125 ms 202604 KB Output is correct
17 Correct 125 ms 202476 KB Output is correct
18 Correct 125 ms 202604 KB Output is correct
19 Correct 126 ms 202604 KB Output is correct
20 Correct 123 ms 202476 KB Output is correct
21 Correct 123 ms 202732 KB Output is correct
22 Correct 132 ms 202604 KB Output is correct
23 Correct 124 ms 202604 KB Output is correct
24 Correct 123 ms 202604 KB Output is correct
25 Correct 126 ms 202476 KB Output is correct
26 Correct 126 ms 202604 KB Output is correct
27 Correct 126 ms 202476 KB Output is correct
28 Correct 124 ms 202476 KB Output is correct
29 Correct 132 ms 202476 KB Output is correct
30 Correct 123 ms 202476 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 202348 KB Output is correct
2 Correct 124 ms 202348 KB Output is correct
3 Correct 123 ms 202348 KB Output is correct
4 Correct 121 ms 202348 KB Output is correct
5 Correct 130 ms 202468 KB Output is correct
6 Correct 124 ms 202624 KB Output is correct
7 Correct 123 ms 202604 KB Output is correct
8 Correct 122 ms 202476 KB Output is correct
9 Correct 123 ms 202604 KB Output is correct
10 Correct 123 ms 202476 KB Output is correct
11 Correct 124 ms 202604 KB Output is correct
12 Correct 123 ms 202476 KB Output is correct
13 Correct 124 ms 202496 KB Output is correct
14 Correct 124 ms 202732 KB Output is correct
15 Correct 126 ms 202604 KB Output is correct
16 Correct 125 ms 202604 KB Output is correct
17 Correct 125 ms 202476 KB Output is correct
18 Correct 125 ms 202604 KB Output is correct
19 Correct 126 ms 202604 KB Output is correct
20 Correct 123 ms 202476 KB Output is correct
21 Correct 123 ms 202732 KB Output is correct
22 Correct 132 ms 202604 KB Output is correct
23 Correct 124 ms 202604 KB Output is correct
24 Correct 123 ms 202604 KB Output is correct
25 Correct 126 ms 202476 KB Output is correct
26 Correct 126 ms 202604 KB Output is correct
27 Correct 126 ms 202476 KB Output is correct
28 Correct 124 ms 202476 KB Output is correct
29 Correct 132 ms 202476 KB Output is correct
30 Correct 123 ms 202476 KB Output is correct
31 Correct 636 ms 224072 KB Output is correct
32 Correct 247 ms 216232 KB Output is correct
33 Correct 596 ms 220232 KB Output is correct
34 Correct 591 ms 220360 KB Output is correct
35 Correct 662 ms 223944 KB Output is correct
36 Correct 630 ms 223952 KB Output is correct
37 Correct 507 ms 219208 KB Output is correct
38 Correct 467 ms 219080 KB Output is correct
39 Correct 403 ms 219044 KB Output is correct
40 Correct 421 ms 219172 KB Output is correct
41 Correct 521 ms 219464 KB Output is correct
42 Correct 532 ms 219336 KB Output is correct
43 Correct 197 ms 216152 KB Output is correct
44 Correct 523 ms 219624 KB Output is correct
45 Correct 516 ms 219592 KB Output is correct
46 Correct 491 ms 219592 KB Output is correct
47 Correct 359 ms 218568 KB Output is correct
48 Correct 369 ms 218472 KB Output is correct
49 Correct 374 ms 219080 KB Output is correct
50 Correct 391 ms 219080 KB Output is correct
51 Correct 393 ms 218952 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2399 ms 324020 KB Output is correct
2 Correct 2509 ms 320884 KB Output is correct
3 Correct 2160 ms 381160 KB Output is correct
4 Correct 2298 ms 342360 KB Output is correct
5 Correct 2483 ms 320516 KB Output is correct
6 Correct 2487 ms 320748 KB Output is correct
7 Correct 2021 ms 380992 KB Output is correct
8 Correct 1951 ms 342492 KB Output is correct
9 Correct 1976 ms 328964 KB Output is correct
10 Correct 2103 ms 322176 KB Output is correct
11 Correct 1421 ms 319004 KB Output is correct
12 Correct 1470 ms 321428 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3488 ms 309656 KB Output is correct
2 Correct 678 ms 274480 KB Output is correct
3 Correct 3500 ms 320072 KB Output is correct
4 Correct 2835 ms 378996 KB Output is correct
5 Correct 3399 ms 331448 KB Output is correct
6 Correct 3242 ms 339320 KB Output is correct
7 Correct 3309 ms 319620 KB Output is correct
8 Correct 3380 ms 320048 KB Output is correct
9 Correct 2613 ms 380060 KB Output is correct
10 Correct 2980 ms 336784 KB Output is correct
11 Correct 3029 ms 325448 KB Output is correct
12 Correct 3008 ms 321520 KB Output is correct
13 Correct 1591 ms 316956 KB Output is correct
14 Correct 1576 ms 315728 KB Output is correct
15 Correct 1750 ms 318596 KB Output is correct
16 Correct 1919 ms 320792 KB Output is correct
17 Correct 1912 ms 317976 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 202348 KB Output is correct
2 Correct 124 ms 202348 KB Output is correct
3 Correct 123 ms 202348 KB Output is correct
4 Correct 121 ms 202348 KB Output is correct
5 Correct 130 ms 202468 KB Output is correct
6 Correct 124 ms 202624 KB Output is correct
7 Correct 123 ms 202604 KB Output is correct
8 Correct 122 ms 202476 KB Output is correct
9 Correct 123 ms 202604 KB Output is correct
10 Correct 123 ms 202476 KB Output is correct
11 Correct 124 ms 202604 KB Output is correct
12 Correct 123 ms 202476 KB Output is correct
13 Correct 124 ms 202496 KB Output is correct
14 Correct 124 ms 202732 KB Output is correct
15 Correct 126 ms 202604 KB Output is correct
16 Correct 125 ms 202604 KB Output is correct
17 Correct 125 ms 202476 KB Output is correct
18 Correct 125 ms 202604 KB Output is correct
19 Correct 126 ms 202604 KB Output is correct
20 Correct 123 ms 202476 KB Output is correct
21 Correct 123 ms 202732 KB Output is correct
22 Correct 132 ms 202604 KB Output is correct
23 Correct 124 ms 202604 KB Output is correct
24 Correct 123 ms 202604 KB Output is correct
25 Correct 126 ms 202476 KB Output is correct
26 Correct 126 ms 202604 KB Output is correct
27 Correct 126 ms 202476 KB Output is correct
28 Correct 124 ms 202476 KB Output is correct
29 Correct 132 ms 202476 KB Output is correct
30 Correct 123 ms 202476 KB Output is correct
31 Correct 636 ms 224072 KB Output is correct
32 Correct 247 ms 216232 KB Output is correct
33 Correct 596 ms 220232 KB Output is correct
34 Correct 591 ms 220360 KB Output is correct
35 Correct 662 ms 223944 KB Output is correct
36 Correct 630 ms 223952 KB Output is correct
37 Correct 507 ms 219208 KB Output is correct
38 Correct 467 ms 219080 KB Output is correct
39 Correct 403 ms 219044 KB Output is correct
40 Correct 421 ms 219172 KB Output is correct
41 Correct 521 ms 219464 KB Output is correct
42 Correct 532 ms 219336 KB Output is correct
43 Correct 197 ms 216152 KB Output is correct
44 Correct 523 ms 219624 KB Output is correct
45 Correct 516 ms 219592 KB Output is correct
46 Correct 491 ms 219592 KB Output is correct
47 Correct 359 ms 218568 KB Output is correct
48 Correct 369 ms 218472 KB Output is correct
49 Correct 374 ms 219080 KB Output is correct
50 Correct 391 ms 219080 KB Output is correct
51 Correct 393 ms 218952 KB Output is correct
52 Correct 549 ms 234952 KB Output is correct
53 Correct 558 ms 228040 KB Output is correct
54 Correct 606 ms 227156 KB Output is correct
55 Correct 519 ms 224072 KB Output is correct
56 Correct 517 ms 226912 KB Output is correct
57 Correct 524 ms 219976 KB Output is correct
58 Correct 534 ms 223816 KB Output is correct
59 Correct 543 ms 226760 KB Output is correct
60 Correct 530 ms 219924 KB Output is correct
61 Correct 221 ms 225232 KB Output is correct
62 Correct 546 ms 235176 KB Output is correct
63 Correct 588 ms 228424 KB Output is correct
64 Correct 582 ms 225736 KB Output is correct
65 Correct 578 ms 220616 KB Output is correct
66 Correct 536 ms 222176 KB Output is correct
67 Correct 286 ms 217560 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 202348 KB Output is correct
2 Correct 124 ms 202348 KB Output is correct
3 Correct 123 ms 202348 KB Output is correct
4 Correct 121 ms 202348 KB Output is correct
5 Correct 130 ms 202468 KB Output is correct
6 Correct 124 ms 202624 KB Output is correct
7 Correct 123 ms 202604 KB Output is correct
8 Correct 122 ms 202476 KB Output is correct
9 Correct 123 ms 202604 KB Output is correct
10 Correct 123 ms 202476 KB Output is correct
11 Correct 124 ms 202604 KB Output is correct
12 Correct 123 ms 202476 KB Output is correct
13 Correct 124 ms 202496 KB Output is correct
14 Correct 124 ms 202732 KB Output is correct
15 Correct 126 ms 202604 KB Output is correct
16 Correct 125 ms 202604 KB Output is correct
17 Correct 125 ms 202476 KB Output is correct
18 Correct 125 ms 202604 KB Output is correct
19 Correct 126 ms 202604 KB Output is correct
20 Correct 123 ms 202476 KB Output is correct
21 Correct 123 ms 202732 KB Output is correct
22 Correct 132 ms 202604 KB Output is correct
23 Correct 124 ms 202604 KB Output is correct
24 Correct 123 ms 202604 KB Output is correct
25 Correct 126 ms 202476 KB Output is correct
26 Correct 126 ms 202604 KB Output is correct
27 Correct 126 ms 202476 KB Output is correct
28 Correct 124 ms 202476 KB Output is correct
29 Correct 132 ms 202476 KB Output is correct
30 Correct 123 ms 202476 KB Output is correct
31 Correct 636 ms 224072 KB Output is correct
32 Correct 247 ms 216232 KB Output is correct
33 Correct 596 ms 220232 KB Output is correct
34 Correct 591 ms 220360 KB Output is correct
35 Correct 662 ms 223944 KB Output is correct
36 Correct 630 ms 223952 KB Output is correct
37 Correct 507 ms 219208 KB Output is correct
38 Correct 467 ms 219080 KB Output is correct
39 Correct 403 ms 219044 KB Output is correct
40 Correct 421 ms 219172 KB Output is correct
41 Correct 521 ms 219464 KB Output is correct
42 Correct 532 ms 219336 KB Output is correct
43 Correct 197 ms 216152 KB Output is correct
44 Correct 523 ms 219624 KB Output is correct
45 Correct 516 ms 219592 KB Output is correct
46 Correct 491 ms 219592 KB Output is correct
47 Correct 359 ms 218568 KB Output is correct
48 Correct 369 ms 218472 KB Output is correct
49 Correct 374 ms 219080 KB Output is correct
50 Correct 391 ms 219080 KB Output is correct
51 Correct 393 ms 218952 KB Output is correct
52 Correct 2399 ms 324020 KB Output is correct
53 Correct 2509 ms 320884 KB Output is correct
54 Correct 2160 ms 381160 KB Output is correct
55 Correct 2298 ms 342360 KB Output is correct
56 Correct 2483 ms 320516 KB Output is correct
57 Correct 2487 ms 320748 KB Output is correct
58 Correct 2021 ms 380992 KB Output is correct
59 Correct 1951 ms 342492 KB Output is correct
60 Correct 1976 ms 328964 KB Output is correct
61 Correct 2103 ms 322176 KB Output is correct
62 Correct 1421 ms 319004 KB Output is correct
63 Correct 1470 ms 321428 KB Output is correct
64 Correct 3488 ms 309656 KB Output is correct
65 Correct 678 ms 274480 KB Output is correct
66 Correct 3500 ms 320072 KB Output is correct
67 Correct 2835 ms 378996 KB Output is correct
68 Correct 3399 ms 331448 KB Output is correct
69 Correct 3242 ms 339320 KB Output is correct
70 Correct 3309 ms 319620 KB Output is correct
71 Correct 3380 ms 320048 KB Output is correct
72 Correct 2613 ms 380060 KB Output is correct
73 Correct 2980 ms 336784 KB Output is correct
74 Correct 3029 ms 325448 KB Output is correct
75 Correct 3008 ms 321520 KB Output is correct
76 Correct 1591 ms 316956 KB Output is correct
77 Correct 1576 ms 315728 KB Output is correct
78 Correct 1750 ms 318596 KB Output is correct
79 Correct 1919 ms 320792 KB Output is correct
80 Correct 1912 ms 317976 KB Output is correct
81 Correct 549 ms 234952 KB Output is correct
82 Correct 558 ms 228040 KB Output is correct
83 Correct 606 ms 227156 KB Output is correct
84 Correct 519 ms 224072 KB Output is correct
85 Correct 517 ms 226912 KB Output is correct
86 Correct 524 ms 219976 KB Output is correct
87 Correct 534 ms 223816 KB Output is correct
88 Correct 543 ms 226760 KB Output is correct
89 Correct 530 ms 219924 KB Output is correct
90 Correct 221 ms 225232 KB Output is correct
91 Correct 546 ms 235176 KB Output is correct
92 Correct 588 ms 228424 KB Output is correct
93 Correct 582 ms 225736 KB Output is correct
94 Correct 578 ms 220616 KB Output is correct
95 Correct 536 ms 222176 KB Output is correct
96 Correct 286 ms 217560 KB Output is correct
97 Correct 2790 ms 380980 KB Output is correct
98 Correct 735 ms 274984 KB Output is correct
99 Correct 3289 ms 304032 KB Output is correct
100 Correct 2753 ms 345440 KB Output is correct
101 Correct 3293 ms 341128 KB Output is correct
102 Correct 3474 ms 322100 KB Output is correct
103 Correct 2626 ms 304064 KB Output is correct
104 Correct 2538 ms 304004 KB Output is correct
105 Correct 1797 ms 303760 KB Output is correct
106 Correct 1888 ms 303668 KB Output is correct
107 Correct 2748 ms 325580 KB Output is correct
108 Correct 2703 ms 339724 KB Output is correct
109 Correct 2834 ms 307256 KB Output is correct
110 Correct 2874 ms 324996 KB Output is correct
111 Correct 2882 ms 339208 KB Output is correct
112 Correct 2943 ms 306948 KB Output is correct
113 Correct 660 ms 347588 KB Output is correct
114 Correct 2847 ms 381344 KB Output is correct
115 Correct 3217 ms 347980 KB Output is correct
116 Correct 3305 ms 333888 KB Output is correct
117 Correct 3342 ms 308980 KB Output is correct
118 Correct 3060 ms 306620 KB Output is correct
119 Correct 1022 ms 278552 KB Output is correct
120 Correct 1255 ms 296812 KB Output is correct
121 Correct 1411 ms 301656 KB Output is correct
122 Correct 1457 ms 301060 KB Output is correct
123 Correct 1584 ms 303144 KB Output is correct
124 Correct 1818 ms 304720 KB Output is correct
125 Correct 1796 ms 303640 KB Output is correct
126 Correct 1866 ms 304592 KB Output is correct