oj.uz

Submission #365466

# Submission time Handle Problem Language Result Execution time Memory
365466 2021-02-11T17:28:52 Z doowey New Home (APIO18_new_home) C++17
12 / 100
 5000 ms 980012 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 = 6*N;
map<int, int> segt[M * 2][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 230 ms 352620 KB Output is correct
2 Correct 245 ms 352620 KB Output is correct
3 Correct 263 ms 352672 KB Output is correct
4 Correct 245 ms 352620 KB Output is correct
5 Correct 242 ms 353096 KB Output is correct
6 Correct 243 ms 353104 KB Output is correct
7 Correct 249 ms 353004 KB Output is correct
8 Correct 272 ms 353108 KB Output is correct
9 Correct 246 ms 353260 KB Output is correct
10 Correct 242 ms 353004 KB Output is correct
11 Correct 244 ms 352964 KB Output is correct
12 Correct 242 ms 353024 KB Output is correct
13 Correct 244 ms 352952 KB Output is correct
14 Correct 243 ms 353008 KB Output is correct
15 Correct 252 ms 353024 KB Output is correct
16 Correct 255 ms 353052 KB Output is correct
17 Correct 257 ms 353004 KB Output is correct
18 Correct 256 ms 353004 KB Output is correct
19 Correct 240 ms 353108 KB Output is correct
20 Correct 242 ms 353132 KB Output is correct
21 Correct 241 ms 353004 KB Output is correct
22 Correct 263 ms 353260 KB Output is correct
23 Correct 249 ms 353104 KB Output is correct
24 Correct 238 ms 353108 KB Output is correct
25 Correct 244 ms 352976 KB Output is correct
26 Correct 238 ms 353132 KB Output is correct
27 Correct 238 ms 353004 KB Output is correct
28 Correct 238 ms 353004 KB Output is correct
29 Correct 242 ms 353004 KB Output is correct
30 Correct 254 ms 352876 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 352620 KB Output is correct
2 Correct 245 ms 352620 KB Output is correct
3 Correct 263 ms 352672 KB Output is correct
4 Correct 245 ms 352620 KB Output is correct
5 Correct 242 ms 353096 KB Output is correct
6 Correct 243 ms 353104 KB Output is correct
7 Correct 249 ms 353004 KB Output is correct
8 Correct 272 ms 353108 KB Output is correct
9 Correct 246 ms 353260 KB Output is correct
10 Correct 242 ms 353004 KB Output is correct
11 Correct 244 ms 352964 KB Output is correct
12 Correct 242 ms 353024 KB Output is correct
13 Correct 244 ms 352952 KB Output is correct
14 Correct 243 ms 353008 KB Output is correct
15 Correct 252 ms 353024 KB Output is correct
16 Correct 255 ms 353052 KB Output is correct
17 Correct 257 ms 353004 KB Output is correct
18 Correct 256 ms 353004 KB Output is correct
19 Correct 240 ms 353108 KB Output is correct
20 Correct 242 ms 353132 KB Output is correct
21 Correct 241 ms 353004 KB Output is correct
22 Correct 263 ms 353260 KB Output is correct
23 Correct 249 ms 353104 KB Output is correct
24 Correct 238 ms 353108 KB Output is correct
25 Correct 244 ms 352976 KB Output is correct
26 Correct 238 ms 353132 KB Output is correct
27 Correct 238 ms 353004 KB Output is correct
28 Correct 238 ms 353004 KB Output is correct
29 Correct 242 ms 353004 KB Output is correct
30 Correct 254 ms 352876 KB Output is correct
31 Correct 4061 ms 426608 KB Output is correct
32 Correct 440 ms 382896 KB Output is correct
33 Correct 1890 ms 386436 KB Output is correct
34 Correct 3885 ms 397196 KB Output is correct
35 Correct 3092 ms 417912 KB Output is correct
36 Correct 1803 ms 399328 KB Output is correct
37 Correct 1598 ms 382896 KB Output is correct
38 Correct 1262 ms 383040 KB Output is correct
39 Correct 1106 ms 383052 KB Output is correct
40 Correct 1103 ms 382924 KB Output is correct
41 Correct 2319 ms 382924 KB Output is correct
42 Correct 2345 ms 382952 KB Output is correct
43 Correct 336 ms 382924 KB Output is correct
44 Correct 2172 ms 382936 KB Output is correct
45 Correct 1862 ms 382924 KB Output is correct
46 Correct 1565 ms 382928 KB Output is correct
47 Correct 1103 ms 382924 KB Output is correct
48 Correct 996 ms 382796 KB Output is correct
49 Correct 1250 ms 382840 KB Output is correct
50 Correct 1715 ms 382928 KB Output is correct
51 Correct 1233 ms 382848 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1879 ms 975560 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1962 ms 980012 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 352620 KB Output is correct
2 Correct 245 ms 352620 KB Output is correct
3 Correct 263 ms 352672 KB Output is correct
4 Correct 245 ms 352620 KB Output is correct
5 Correct 242 ms 353096 KB Output is correct
6 Correct 243 ms 353104 KB Output is correct
7 Correct 249 ms 353004 KB Output is correct
8 Correct 272 ms 353108 KB Output is correct
9 Correct 246 ms 353260 KB Output is correct
10 Correct 242 ms 353004 KB Output is correct
11 Correct 244 ms 352964 KB Output is correct
12 Correct 242 ms 353024 KB Output is correct
13 Correct 244 ms 352952 KB Output is correct
14 Correct 243 ms 353008 KB Output is correct
15 Correct 252 ms 353024 KB Output is correct
16 Correct 255 ms 353052 KB Output is correct
17 Correct 257 ms 353004 KB Output is correct
18 Correct 256 ms 353004 KB Output is correct
19 Correct 240 ms 353108 KB Output is correct
20 Correct 242 ms 353132 KB Output is correct
21 Correct 241 ms 353004 KB Output is correct
22 Correct 263 ms 353260 KB Output is correct
23 Correct 249 ms 353104 KB Output is correct
24 Correct 238 ms 353108 KB Output is correct
25 Correct 244 ms 352976 KB Output is correct
26 Correct 238 ms 353132 KB Output is correct
27 Correct 238 ms 353004 KB Output is correct
28 Correct 238 ms 353004 KB Output is correct
29 Correct 242 ms 353004 KB Output is correct
30 Correct 254 ms 352876 KB Output is correct
31 Correct 4061 ms 426608 KB Output is correct
32 Correct 440 ms 382896 KB Output is correct
33 Correct 1890 ms 386436 KB Output is correct
34 Correct 3885 ms 397196 KB Output is correct
35 Correct 3092 ms 417912 KB Output is correct
36 Correct 1803 ms 399328 KB Output is correct
37 Correct 1598 ms 382896 KB Output is correct
38 Correct 1262 ms 383040 KB Output is correct
39 Correct 1106 ms 383052 KB Output is correct
40 Correct 1103 ms 382924 KB Output is correct
41 Correct 2319 ms 382924 KB Output is correct
42 Correct 2345 ms 382952 KB Output is correct
43 Correct 336 ms 382924 KB Output is correct
44 Correct 2172 ms 382936 KB Output is correct
45 Correct 1862 ms 382924 KB Output is correct
46 Correct 1565 ms 382928 KB Output is correct
47 Correct 1103 ms 382924 KB Output is correct
48 Correct 996 ms 382796 KB Output is correct
49 Correct 1250 ms 382840 KB Output is correct
50 Correct 1715 ms 382928 KB Output is correct
51 Correct 1233 ms 382848 KB Output is correct
52 Correct 2841 ms 481488 KB Output is correct
53 Correct 2817 ms 420892 KB Output is correct
54 Correct 4770 ms 461484 KB Output is correct
55 Correct 2805 ms 412680 KB Output is correct
56 Correct 2848 ms 430324 KB Output is correct
57 Correct 2706 ms 387480 KB Output is correct
58 Correct 3092 ms 412704 KB Output is correct
59 Correct 3331 ms 430132 KB Output is correct
60 Correct 3040 ms 387544 KB Output is correct
61 Correct 371 ms 390096 KB Output is correct
62 Correct 2944 ms 481732 KB Output is correct
63 Correct 4249 ms 456180 KB Output is correct
64 Correct 4550 ms 438460 KB Output is correct
65 Execution timed out 5001 ms 396836 KB Time limit exceeded
66 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 352620 KB Output is correct
2 Correct 245 ms 352620 KB Output is correct
3 Correct 263 ms 352672 KB Output is correct
4 Correct 245 ms 352620 KB Output is correct
5 Correct 242 ms 353096 KB Output is correct
6 Correct 243 ms 353104 KB Output is correct
7 Correct 249 ms 353004 KB Output is correct
8 Correct 272 ms 353108 KB Output is correct
9 Correct 246 ms 353260 KB Output is correct
10 Correct 242 ms 353004 KB Output is correct
11 Correct 244 ms 352964 KB Output is correct
12 Correct 242 ms 353024 KB Output is correct
13 Correct 244 ms 352952 KB Output is correct
14 Correct 243 ms 353008 KB Output is correct
15 Correct 252 ms 353024 KB Output is correct
16 Correct 255 ms 353052 KB Output is correct
17 Correct 257 ms 353004 KB Output is correct
18 Correct 256 ms 353004 KB Output is correct
19 Correct 240 ms 353108 KB Output is correct
20 Correct 242 ms 353132 KB Output is correct
21 Correct 241 ms 353004 KB Output is correct
22 Correct 263 ms 353260 KB Output is correct
23 Correct 249 ms 353104 KB Output is correct
24 Correct 238 ms 353108 KB Output is correct
25 Correct 244 ms 352976 KB Output is correct
26 Correct 238 ms 353132 KB Output is correct
27 Correct 238 ms 353004 KB Output is correct
28 Correct 238 ms 353004 KB Output is correct
29 Correct 242 ms 353004 KB Output is correct
30 Correct 254 ms 352876 KB Output is correct
31 Correct 4061 ms 426608 KB Output is correct
32 Correct 440 ms 382896 KB Output is correct
33 Correct 1890 ms 386436 KB Output is correct
34 Correct 3885 ms 397196 KB Output is correct
35 Correct 3092 ms 417912 KB Output is correct
36 Correct 1803 ms 399328 KB Output is correct
37 Correct 1598 ms 382896 KB Output is correct
38 Correct 1262 ms 383040 KB Output is correct
39 Correct 1106 ms 383052 KB Output is correct
40 Correct 1103 ms 382924 KB Output is correct
41 Correct 2319 ms 382924 KB Output is correct
42 Correct 2345 ms 382952 KB Output is correct
43 Correct 336 ms 382924 KB Output is correct
44 Correct 2172 ms 382936 KB Output is correct
45 Correct 1862 ms 382924 KB Output is correct
46 Correct 1565 ms 382928 KB Output is correct
47 Correct 1103 ms 382924 KB Output is correct
48 Correct 996 ms 382796 KB Output is correct
49 Correct 1250 ms 382840 KB Output is correct
50 Correct 1715 ms 382928 KB Output is correct
51 Correct 1233 ms 382848 KB Output is correct
52 Runtime error 1879 ms 975560 KB Execution killed with signal 11
53 Halted 0 ms 0 KB -