oj.uz

Submission #365455

# Submission time Handle Problem Language Result Execution time Memory
365455 2021-02-11T17:18:05 Z doowey New Home (APIO18_new_home) C++14
12 / 100
 5000 ms 1048580 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 tt;
    int lef;
    int rig;
    int dir;
    int val;
    int add;
    bool operator< (const lin &aq) const {
        return tt < aq.tt;
    }
};

int cur;

vector<lin> lis;

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

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];

const int M = (int)2e6;
map<int, int> segt[M * 4][2];

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

int m;

void update(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){
            segt[node][dir][v] ++ ;
        }
        else{
            segt[node][dir][v] -- ;
            if(segt[node][dir][v] == 0){
                segt[node][dir].erase(v);
            }
        }
        return;
    }
    int mid = (cl + cr) / 2;
    update(node * 2, cl, mid, tl, tr, dir, v, mode);
    update(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(!segt[node][0].empty()){
        auto it = segt[node][0].end();
        -- it;
        vl = max(vl, (it->fi) + cors[pos]);
    }
    if(!segt[node][1].empty()){
        auto it = segt[node][1].end();
        -- it;
        vl = max(vl, (it->fi) - cors[pos]);
    }
    if(cl == cr) return vl;
    int mid = (cl + cr) / 2;
    if(mid >= pos)
        return max(vl, get(node * 2, cl, mid, pos));
    else
        return max(vl, get(node * 2 + 1, mid + 1, cr, pos));

}

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();
    int it = 0;
    int gq;
    for(int i = 0; i < q ; i ++ ){
        while(it < lis.size() && lis[it].tt <= ord[i].fi){
            update(1, 0, m - 1, getid(lis[it].lef), getid(lis[it].rig), lis[it].dir, lis[it].val, lis[it].add);
            it ++ ;
        }

        gq = get(1, 0, m - 1, getid(xx[ord[i].se]));
        gq /= 2;
        if(gq > (int)1e8){
            soln[ord[i].se] = -1;
        }
        else{
            soln[ord[i].se] = gq;
        }
    }
    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:154: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]
  154 |     for(int i = 0 ; i < eve.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
new_home.cpp:169:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<lin>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         while(it < lis.size() && lis[it].tt <= ord[i].fi){
      |               ~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 766084 KB Output is correct
2 Correct 543 ms 765932 KB Output is correct
3 Correct 489 ms 765932 KB Output is correct
4 Correct 501 ms 766108 KB Output is correct
5 Correct 489 ms 766376 KB Output is correct
6 Correct 489 ms 766344 KB Output is correct
7 Correct 496 ms 766444 KB Output is correct
8 Correct 498 ms 766508 KB Output is correct
9 Correct 493 ms 766572 KB Output is correct
10 Correct 496 ms 766316 KB Output is correct
11 Correct 497 ms 766316 KB Output is correct
12 Correct 546 ms 766404 KB Output is correct
13 Correct 497 ms 766316 KB Output is correct
14 Correct 489 ms 766316 KB Output is correct
15 Correct 490 ms 766316 KB Output is correct
16 Correct 493 ms 766444 KB Output is correct
17 Correct 497 ms 766392 KB Output is correct
18 Correct 494 ms 766316 KB Output is correct
19 Correct 492 ms 766472 KB Output is correct
20 Correct 500 ms 766316 KB Output is correct
21 Correct 497 ms 766444 KB Output is correct
22 Correct 496 ms 766572 KB Output is correct
23 Correct 509 ms 766420 KB Output is correct
24 Correct 502 ms 766572 KB Output is correct
25 Correct 502 ms 766444 KB Output is correct
26 Correct 499 ms 766304 KB Output is correct
27 Correct 491 ms 766316 KB Output is correct
28 Correct 495 ms 766572 KB Output is correct
29 Correct 509 ms 766316 KB Output is correct
30 Correct 511 ms 766188 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 766084 KB Output is correct
2 Correct 543 ms 765932 KB Output is correct
3 Correct 489 ms 765932 KB Output is correct
4 Correct 501 ms 766108 KB Output is correct
5 Correct 489 ms 766376 KB Output is correct
6 Correct 489 ms 766344 KB Output is correct
7 Correct 496 ms 766444 KB Output is correct
8 Correct 498 ms 766508 KB Output is correct
9 Correct 493 ms 766572 KB Output is correct
10 Correct 496 ms 766316 KB Output is correct
11 Correct 497 ms 766316 KB Output is correct
12 Correct 546 ms 766404 KB Output is correct
13 Correct 497 ms 766316 KB Output is correct
14 Correct 489 ms 766316 KB Output is correct
15 Correct 490 ms 766316 KB Output is correct
16 Correct 493 ms 766444 KB Output is correct
17 Correct 497 ms 766392 KB Output is correct
18 Correct 494 ms 766316 KB Output is correct
19 Correct 492 ms 766472 KB Output is correct
20 Correct 500 ms 766316 KB Output is correct
21 Correct 497 ms 766444 KB Output is correct
22 Correct 496 ms 766572 KB Output is correct
23 Correct 509 ms 766420 KB Output is correct
24 Correct 502 ms 766572 KB Output is correct
25 Correct 502 ms 766444 KB Output is correct
26 Correct 499 ms 766304 KB Output is correct
27 Correct 491 ms 766316 KB Output is correct
28 Correct 495 ms 766572 KB Output is correct
29 Correct 509 ms 766316 KB Output is correct
30 Correct 511 ms 766188 KB Output is correct
31 Correct 4208 ms 842580 KB Output is correct
32 Correct 688 ms 797004 KB Output is correct
33 Correct 2117 ms 802408 KB Output is correct
34 Correct 4142 ms 813044 KB Output is correct
35 Correct 3328 ms 833708 KB Output is correct
36 Correct 2013 ms 815268 KB Output is correct
37 Correct 1777 ms 798784 KB Output is correct
38 Correct 1441 ms 798796 KB Output is correct
39 Correct 1286 ms 798796 KB Output is correct
40 Correct 1274 ms 798756 KB Output is correct
41 Correct 2413 ms 798796 KB Output is correct
42 Correct 2558 ms 798912 KB Output is correct
43 Correct 608 ms 798204 KB Output is correct
44 Correct 2368 ms 798784 KB Output is correct
45 Correct 2076 ms 798784 KB Output is correct
46 Correct 1778 ms 798796 KB Output is correct
47 Correct 1341 ms 798540 KB Output is correct
48 Correct 1254 ms 798540 KB Output is correct
49 Correct 1500 ms 798668 KB Output is correct
50 Correct 2033 ms 798924 KB Output is correct
51 Correct 1506 ms 798672 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4652 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 766084 KB Output is correct
2 Correct 543 ms 765932 KB Output is correct
3 Correct 489 ms 765932 KB Output is correct
4 Correct 501 ms 766108 KB Output is correct
5 Correct 489 ms 766376 KB Output is correct
6 Correct 489 ms 766344 KB Output is correct
7 Correct 496 ms 766444 KB Output is correct
8 Correct 498 ms 766508 KB Output is correct
9 Correct 493 ms 766572 KB Output is correct
10 Correct 496 ms 766316 KB Output is correct
11 Correct 497 ms 766316 KB Output is correct
12 Correct 546 ms 766404 KB Output is correct
13 Correct 497 ms 766316 KB Output is correct
14 Correct 489 ms 766316 KB Output is correct
15 Correct 490 ms 766316 KB Output is correct
16 Correct 493 ms 766444 KB Output is correct
17 Correct 497 ms 766392 KB Output is correct
18 Correct 494 ms 766316 KB Output is correct
19 Correct 492 ms 766472 KB Output is correct
20 Correct 500 ms 766316 KB Output is correct
21 Correct 497 ms 766444 KB Output is correct
22 Correct 496 ms 766572 KB Output is correct
23 Correct 509 ms 766420 KB Output is correct
24 Correct 502 ms 766572 KB Output is correct
25 Correct 502 ms 766444 KB Output is correct
26 Correct 499 ms 766304 KB Output is correct
27 Correct 491 ms 766316 KB Output is correct
28 Correct 495 ms 766572 KB Output is correct
29 Correct 509 ms 766316 KB Output is correct
30 Correct 511 ms 766188 KB Output is correct
31 Correct 4208 ms 842580 KB Output is correct
32 Correct 688 ms 797004 KB Output is correct
33 Correct 2117 ms 802408 KB Output is correct
34 Correct 4142 ms 813044 KB Output is correct
35 Correct 3328 ms 833708 KB Output is correct
36 Correct 2013 ms 815268 KB Output is correct
37 Correct 1777 ms 798784 KB Output is correct
38 Correct 1441 ms 798796 KB Output is correct
39 Correct 1286 ms 798796 KB Output is correct
40 Correct 1274 ms 798756 KB Output is correct
41 Correct 2413 ms 798796 KB Output is correct
42 Correct 2558 ms 798912 KB Output is correct
43 Correct 608 ms 798204 KB Output is correct
44 Correct 2368 ms 798784 KB Output is correct
45 Correct 2076 ms 798784 KB Output is correct
46 Correct 1778 ms 798796 KB Output is correct
47 Correct 1341 ms 798540 KB Output is correct
48 Correct 1254 ms 798540 KB Output is correct
49 Correct 1500 ms 798668 KB Output is correct
50 Correct 2033 ms 798924 KB Output is correct
51 Correct 1506 ms 798672 KB Output is correct
52 Correct 3093 ms 897796 KB Output is correct
53 Correct 2972 ms 837208 KB Output is correct
54 Correct 4901 ms 877732 KB Output is correct
55 Correct 3221 ms 828836 KB Output is correct
56 Correct 3259 ms 846496 KB Output is correct
57 Correct 3097 ms 803684 KB Output is correct
58 Correct 3898 ms 829040 KB Output is correct
59 Correct 3800 ms 846500 KB Output is correct
60 Correct 3359 ms 803748 KB Output is correct
61 Correct 626 ms 805964 KB Output is correct
62 Correct 3072 ms 897928 KB Output is correct
63 Correct 4326 ms 872456 KB Output is correct
64 Correct 4766 ms 854820 KB Output is correct
65 Execution timed out 5016 ms 813236 KB Time limit exceeded
66 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 766084 KB Output is correct
2 Correct 543 ms 765932 KB Output is correct
3 Correct 489 ms 765932 KB Output is correct
4 Correct 501 ms 766108 KB Output is correct
5 Correct 489 ms 766376 KB Output is correct
6 Correct 489 ms 766344 KB Output is correct
7 Correct 496 ms 766444 KB Output is correct
8 Correct 498 ms 766508 KB Output is correct
9 Correct 493 ms 766572 KB Output is correct
10 Correct 496 ms 766316 KB Output is correct
11 Correct 497 ms 766316 KB Output is correct
12 Correct 546 ms 766404 KB Output is correct
13 Correct 497 ms 766316 KB Output is correct
14 Correct 489 ms 766316 KB Output is correct
15 Correct 490 ms 766316 KB Output is correct
16 Correct 493 ms 766444 KB Output is correct
17 Correct 497 ms 766392 KB Output is correct
18 Correct 494 ms 766316 KB Output is correct
19 Correct 492 ms 766472 KB Output is correct
20 Correct 500 ms 766316 KB Output is correct
21 Correct 497 ms 766444 KB Output is correct
22 Correct 496 ms 766572 KB Output is correct
23 Correct 509 ms 766420 KB Output is correct
24 Correct 502 ms 766572 KB Output is correct
25 Correct 502 ms 766444 KB Output is correct
26 Correct 499 ms 766304 KB Output is correct
27 Correct 491 ms 766316 KB Output is correct
28 Correct 495 ms 766572 KB Output is correct
29 Correct 509 ms 766316 KB Output is correct
30 Correct 511 ms 766188 KB Output is correct
31 Correct 4208 ms 842580 KB Output is correct
32 Correct 688 ms 797004 KB Output is correct
33 Correct 2117 ms 802408 KB Output is correct
34 Correct 4142 ms 813044 KB Output is correct
35 Correct 3328 ms 833708 KB Output is correct
36 Correct 2013 ms 815268 KB Output is correct
37 Correct 1777 ms 798784 KB Output is correct
38 Correct 1441 ms 798796 KB Output is correct
39 Correct 1286 ms 798796 KB Output is correct
40 Correct 1274 ms 798756 KB Output is correct
41 Correct 2413 ms 798796 KB Output is correct
42 Correct 2558 ms 798912 KB Output is correct
43 Correct 608 ms 798204 KB Output is correct
44 Correct 2368 ms 798784 KB Output is correct
45 Correct 2076 ms 798784 KB Output is correct
46 Correct 1778 ms 798796 KB Output is correct
47 Correct 1341 ms 798540 KB Output is correct
48 Correct 1254 ms 798540 KB Output is correct
49 Correct 1500 ms 798668 KB Output is correct
50 Correct 2033 ms 798924 KB Output is correct
51 Correct 1506 ms 798672 KB Output is correct
52 Runtime error 4652 ms 1048580 KB Execution killed with signal 9
53 Halted 0 ms 0 KB -