oj.uz

Submission #233120

# Submission time Handle Problem Language Result Execution time Memory
233120 2020-05-19T11:50:41 Z nvmdava New Home (APIO18_new_home) C++17
100 / 100
 2687 ms 125252 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 2000005
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
 
int x[N], ans[N], y[N], l[N], t[N], a[N], b[N];
int n, k, q;
vector<int> tmp;
 
vector<pair<int, int> > sh[N];
map<int, int> in, ok;
vector<pair<pair<int, int>, pair<int, int> > > lol;
int seg[N];
int hel;
void update(int id, int l, int r, int L, int R, int v){
    if(l >= L && r <= R){
        seg[id] = max(seg[id], v);
        return;
    }
    if(l > R || r < L) return;
    int m = (l + r) >> 1;
    update(id << 1, l, m, L, R, v);
    update(id << 1 | 1, m + 1, r, L, R, v);
}
 
int query(int id, int l, int r, int x){
    if(x < l || x > r) return 0;
    if(l == r) return seg[id];
    int m = (l + r) >> 1;
    return max(seg[id], max(query(id << 1, l, m, x), query(id << 1 | 1, m + 1, r, x)));
}
 
void solve(){
    for(int i = 1; i <= k; ++i){
        in.clear();
        in[INF] = 1;
        in[-INF] = 1;
        for(auto& x : sh[i]){
            if(x.ss > 0){
                if(++ok[x.ss] >= 2)
                    continue;
                auto r = in.insert({x.ss, x.ff}).ff;
                auto l = r++;
                auto it = l--;
                if(r -> ss < x.ff && r -> ff > 0)
                    lol.push_back({{(r -> ff + l -> ff) / 2, r -> ff}, {r -> ss, x.ff - 1}});
                r -> ss = x.ff;
            } else {
                if(--ok[-x.ss] > 0)
                    continue;
                ok.erase(-x.ss);
                auto r = in.find(-x.ss);
                auto l = r++;
                auto it = l--;
                if(it -> ss < x.ff && it -> ff > 0)
                    lol.push_back({{(it -> ff + l -> ff) / 2, it -> ff}, {it -> ss, x.ff - 1}});
                if(r -> ss < x.ff && r -> ff > 0)
                    lol.push_back({{(it -> ff + r -> ff) / 2, r -> ff}, {r -> ss, x.ff - 1}});
                in[r -> ff] = x.ff;
                in.erase(it);
            }
        }
        auto r = in.begin();
        auto l = r++;
        if(r -> ss <= hel && r -> ff > 0)
            lol.push_back({{(r -> ff + l -> ff) / 2, r -> ff}, {r -> ss, hel}});
    }
    for(int i = 1; i <= q; ++i)
        lol.push_back({{l[i], 1'200'000'000}, {i, y[i]}});
    
    sort(lol.begin(), lol.end(), [](const pair<pair<int, int>, pair<int, int> >& lhs, const pair<pair<int, int>, pair<int, int> >& rhs){
        return lhs.ff < rhs.ff;
    });
    for(auto& x : lol){
        if(x.ff.ss != 1'200'000'000)
            update(1, 1, hel, x.ss.ff, x.ss.ss, x.ff.ss);
        else
            ans[x.ss.ff] = max(ans[x.ss.ff], query(1, 1, hel, x.ss.ss) - x.ff.ff);
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    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];
        l[i] <<= 1;
        tmp.push_back(y[i]);
    }
    sort(tmp.begin(), tmp.end());
    tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
    hel = tmp.size();
    for(int i = 1; i <= q; ++i)
        y[i] = upper_bound(tmp.begin(), tmp.end(), y[i]) - tmp.begin();
    for(int i = 1; i <= n; ++i){
        a[i] = lower_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin() + 1;
        b[i] = lower_bound(tmp.begin(), tmp.end(), b[i] + 1) - tmp.begin() + 1;
        if(a[i] < b[i]){
            x[i] <<= 1;
            sh[t[i]].push_back({a[i], x[i]});
            sh[t[i]].push_back({b[i], -x[i]});
        }
    }
 
    for(int i = 1; i <= k; ++i)
        sort(sh[i].begin(), sh[i].end(), [](const pair<int, int>& lhs, const pair<int, int>& rhs){
            return lhs.ff < rhs.ff;
        });
    solve();

    memset(seg, 0, sizeof seg);
    lol.clear();
    for(int i = 1; i <= q; ++i)
        l[i] = 200'000'002 - l[i];
    for(int i = 1; i <= k; ++i)
        for(auto& x : sh[i])
            if(x.ss > 0)
                x.ss = 200'000'002 - x.ss;
            else
                x.ss = -200'000'002 - x.ss;
    solve();
 
    for(int i = 1; i <= q; ++i){
        if(ans[i] > 400'000'002)
            cout<<"-1\n";
        else
            cout<<ans[i] / 2<<'\n';
    }
}

Compilation message

new_home.cpp: In function 'void solve()':
new_home.cpp:49:22: warning: variable 'it' set but not used [-Wunused-but-set-variable]
                 auto it = l--;
                      ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55168 KB Output is correct
2 Correct 36 ms 55168 KB Output is correct
3 Correct 36 ms 55160 KB Output is correct
4 Correct 37 ms 55160 KB Output is correct
5 Correct 38 ms 55296 KB Output is correct
6 Correct 38 ms 55288 KB Output is correct
7 Correct 38 ms 55296 KB Output is correct
8 Correct 38 ms 55296 KB Output is correct
9 Correct 38 ms 55288 KB Output is correct
10 Correct 38 ms 55288 KB Output is correct
11 Correct 43 ms 55240 KB Output is correct
12 Correct 37 ms 55296 KB Output is correct
13 Correct 38 ms 55288 KB Output is correct
14 Correct 37 ms 55296 KB Output is correct
15 Correct 39 ms 55296 KB Output is correct
16 Correct 38 ms 55296 KB Output is correct
17 Correct 37 ms 55296 KB Output is correct
18 Correct 37 ms 55288 KB Output is correct
19 Correct 38 ms 55296 KB Output is correct
20 Correct 38 ms 55424 KB Output is correct
21 Correct 37 ms 55296 KB Output is correct
22 Correct 37 ms 55288 KB Output is correct
23 Correct 41 ms 55288 KB Output is correct
24 Correct 38 ms 55288 KB Output is correct
25 Correct 37 ms 55296 KB Output is correct
26 Correct 37 ms 55288 KB Output is correct
27 Correct 36 ms 55296 KB Output is correct
28 Correct 38 ms 55288 KB Output is correct
29 Correct 38 ms 55296 KB Output is correct
30 Correct 40 ms 55424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55168 KB Output is correct
2 Correct 36 ms 55168 KB Output is correct
3 Correct 36 ms 55160 KB Output is correct
4 Correct 37 ms 55160 KB Output is correct
5 Correct 38 ms 55296 KB Output is correct
6 Correct 38 ms 55288 KB Output is correct
7 Correct 38 ms 55296 KB Output is correct
8 Correct 38 ms 55296 KB Output is correct
9 Correct 38 ms 55288 KB Output is correct
10 Correct 38 ms 55288 KB Output is correct
11 Correct 43 ms 55240 KB Output is correct
12 Correct 37 ms 55296 KB Output is correct
13 Correct 38 ms 55288 KB Output is correct
14 Correct 37 ms 55296 KB Output is correct
15 Correct 39 ms 55296 KB Output is correct
16 Correct 38 ms 55296 KB Output is correct
17 Correct 37 ms 55296 KB Output is correct
18 Correct 37 ms 55288 KB Output is correct
19 Correct 38 ms 55296 KB Output is correct
20 Correct 38 ms 55424 KB Output is correct
21 Correct 37 ms 55296 KB Output is correct
22 Correct 37 ms 55288 KB Output is correct
23 Correct 41 ms 55288 KB Output is correct
24 Correct 38 ms 55288 KB Output is correct
25 Correct 37 ms 55296 KB Output is correct
26 Correct 37 ms 55288 KB Output is correct
27 Correct 36 ms 55296 KB Output is correct
28 Correct 38 ms 55288 KB Output is correct
29 Correct 38 ms 55296 KB Output is correct
30 Correct 40 ms 55424 KB Output is correct
31 Correct 358 ms 63208 KB Output is correct
32 Correct 96 ms 59240 KB Output is correct
33 Correct 399 ms 62712 KB Output is correct
34 Correct 344 ms 63200 KB Output is correct
35 Correct 377 ms 62560 KB Output is correct
36 Correct 401 ms 62944 KB Output is correct
37 Correct 345 ms 62688 KB Output is correct
38 Correct 359 ms 62424 KB Output is correct
39 Correct 305 ms 62468 KB Output is correct
40 Correct 316 ms 62244 KB Output is correct
41 Correct 295 ms 62560 KB Output is correct
42 Correct 297 ms 62692 KB Output is correct
43 Correct 98 ms 60276 KB Output is correct
44 Correct 297 ms 63128 KB Output is correct
45 Correct 293 ms 62708 KB Output is correct
46 Correct 266 ms 62496 KB Output is correct
47 Correct 238 ms 62052 KB Output is correct
48 Correct 219 ms 61784 KB Output is correct
49 Correct 248 ms 62524 KB Output is correct
50 Correct 273 ms 62944 KB Output is correct
51 Correct 247 ms 62440 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 85684 KB Output is correct
2 Correct 1364 ms 85344 KB Output is correct
3 Correct 1083 ms 90956 KB Output is correct
4 Correct 941 ms 86240 KB Output is correct
5 Correct 2048 ms 115436 KB Output is correct
6 Correct 1502 ms 86344 KB Output is correct
7 Correct 903 ms 91072 KB Output is correct
8 Correct 878 ms 85312 KB Output is correct
9 Correct 910 ms 84108 KB Output is correct
10 Correct 1084 ms 82432 KB Output is correct
11 Correct 1035 ms 83916 KB Output is correct
12 Correct 1000 ms 82836 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 88256 KB Output is correct
2 Correct 314 ms 77400 KB Output is correct
3 Correct 1907 ms 100612 KB Output is correct
4 Correct 1439 ms 111496 KB Output is correct
5 Correct 1342 ms 101828 KB Output is correct
6 Correct 1339 ms 102724 KB Output is correct
7 Correct 2687 ms 125252 KB Output is correct
8 Correct 2128 ms 103412 KB Output is correct
9 Correct 1256 ms 111552 KB Output is correct
10 Correct 1250 ms 102976 KB Output is correct
11 Correct 1308 ms 101404 KB Output is correct
12 Correct 1578 ms 101204 KB Output is correct
13 Correct 1169 ms 99680 KB Output is correct
14 Correct 1212 ms 102080 KB Output is correct
15 Correct 1279 ms 99156 KB Output is correct
16 Correct 1264 ms 100096 KB Output is correct
17 Correct 1428 ms 100160 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55168 KB Output is correct
2 Correct 36 ms 55168 KB Output is correct
3 Correct 36 ms 55160 KB Output is correct
4 Correct 37 ms 55160 KB Output is correct
5 Correct 38 ms 55296 KB Output is correct
6 Correct 38 ms 55288 KB Output is correct
7 Correct 38 ms 55296 KB Output is correct
8 Correct 38 ms 55296 KB Output is correct
9 Correct 38 ms 55288 KB Output is correct
10 Correct 38 ms 55288 KB Output is correct
11 Correct 43 ms 55240 KB Output is correct
12 Correct 37 ms 55296 KB Output is correct
13 Correct 38 ms 55288 KB Output is correct
14 Correct 37 ms 55296 KB Output is correct
15 Correct 39 ms 55296 KB Output is correct
16 Correct 38 ms 55296 KB Output is correct
17 Correct 37 ms 55296 KB Output is correct
18 Correct 37 ms 55288 KB Output is correct
19 Correct 38 ms 55296 KB Output is correct
20 Correct 38 ms 55424 KB Output is correct
21 Correct 37 ms 55296 KB Output is correct
22 Correct 37 ms 55288 KB Output is correct
23 Correct 41 ms 55288 KB Output is correct
24 Correct 38 ms 55288 KB Output is correct
25 Correct 37 ms 55296 KB Output is correct
26 Correct 37 ms 55288 KB Output is correct
27 Correct 36 ms 55296 KB Output is correct
28 Correct 38 ms 55288 KB Output is correct
29 Correct 38 ms 55296 KB Output is correct
30 Correct 40 ms 55424 KB Output is correct
31 Correct 358 ms 63208 KB Output is correct
32 Correct 96 ms 59240 KB Output is correct
33 Correct 399 ms 62712 KB Output is correct
34 Correct 344 ms 63200 KB Output is correct
35 Correct 377 ms 62560 KB Output is correct
36 Correct 401 ms 62944 KB Output is correct
37 Correct 345 ms 62688 KB Output is correct
38 Correct 359 ms 62424 KB Output is correct
39 Correct 305 ms 62468 KB Output is correct
40 Correct 316 ms 62244 KB Output is correct
41 Correct 295 ms 62560 KB Output is correct
42 Correct 297 ms 62692 KB Output is correct
43 Correct 98 ms 60276 KB Output is correct
44 Correct 297 ms 63128 KB Output is correct
45 Correct 293 ms 62708 KB Output is correct
46 Correct 266 ms 62496 KB Output is correct
47 Correct 238 ms 62052 KB Output is correct
48 Correct 219 ms 61784 KB Output is correct
49 Correct 248 ms 62524 KB Output is correct
50 Correct 273 ms 62944 KB Output is correct
51 Correct 247 ms 62440 KB Output is correct
52 Correct 333 ms 64216 KB Output is correct
53 Correct 340 ms 64216 KB Output is correct
54 Correct 331 ms 63200 KB Output is correct
55 Correct 303 ms 63456 KB Output is correct
56 Correct 317 ms 63832 KB Output is correct
57 Correct 298 ms 62952 KB Output is correct
58 Correct 312 ms 63584 KB Output is correct
59 Correct 317 ms 63572 KB Output is correct
60 Correct 305 ms 63200 KB Output is correct
61 Correct 143 ms 62692 KB Output is correct
62 Correct 326 ms 64368 KB Output is correct
63 Correct 331 ms 63572 KB Output is correct
64 Correct 326 ms 63204 KB Output is correct
65 Correct 322 ms 63200 KB Output is correct
66 Correct 305 ms 63200 KB Output is correct
67 Correct 180 ms 62692 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55168 KB Output is correct
2 Correct 36 ms 55168 KB Output is correct
3 Correct 36 ms 55160 KB Output is correct
4 Correct 37 ms 55160 KB Output is correct
5 Correct 38 ms 55296 KB Output is correct
6 Correct 38 ms 55288 KB Output is correct
7 Correct 38 ms 55296 KB Output is correct
8 Correct 38 ms 55296 KB Output is correct
9 Correct 38 ms 55288 KB Output is correct
10 Correct 38 ms 55288 KB Output is correct
11 Correct 43 ms 55240 KB Output is correct
12 Correct 37 ms 55296 KB Output is correct
13 Correct 38 ms 55288 KB Output is correct
14 Correct 37 ms 55296 KB Output is correct
15 Correct 39 ms 55296 KB Output is correct
16 Correct 38 ms 55296 KB Output is correct
17 Correct 37 ms 55296 KB Output is correct
18 Correct 37 ms 55288 KB Output is correct
19 Correct 38 ms 55296 KB Output is correct
20 Correct 38 ms 55424 KB Output is correct
21 Correct 37 ms 55296 KB Output is correct
22 Correct 37 ms 55288 KB Output is correct
23 Correct 41 ms 55288 KB Output is correct
24 Correct 38 ms 55288 KB Output is correct
25 Correct 37 ms 55296 KB Output is correct
26 Correct 37 ms 55288 KB Output is correct
27 Correct 36 ms 55296 KB Output is correct
28 Correct 38 ms 55288 KB Output is correct
29 Correct 38 ms 55296 KB Output is correct
30 Correct 40 ms 55424 KB Output is correct
31 Correct 358 ms 63208 KB Output is correct
32 Correct 96 ms 59240 KB Output is correct
33 Correct 399 ms 62712 KB Output is correct
34 Correct 344 ms 63200 KB Output is correct
35 Correct 377 ms 62560 KB Output is correct
36 Correct 401 ms 62944 KB Output is correct
37 Correct 345 ms 62688 KB Output is correct
38 Correct 359 ms 62424 KB Output is correct
39 Correct 305 ms 62468 KB Output is correct
40 Correct 316 ms 62244 KB Output is correct
41 Correct 295 ms 62560 KB Output is correct
42 Correct 297 ms 62692 KB Output is correct
43 Correct 98 ms 60276 KB Output is correct
44 Correct 297 ms 63128 KB Output is correct
45 Correct 293 ms 62708 KB Output is correct
46 Correct 266 ms 62496 KB Output is correct
47 Correct 238 ms 62052 KB Output is correct
48 Correct 219 ms 61784 KB Output is correct
49 Correct 248 ms 62524 KB Output is correct
50 Correct 273 ms 62944 KB Output is correct
51 Correct 247 ms 62440 KB Output is correct
52 Correct 936 ms 85684 KB Output is correct
53 Correct 1364 ms 85344 KB Output is correct
54 Correct 1083 ms 90956 KB Output is correct
55 Correct 941 ms 86240 KB Output is correct
56 Correct 2048 ms 115436 KB Output is correct
57 Correct 1502 ms 86344 KB Output is correct
58 Correct 903 ms 91072 KB Output is correct
59 Correct 878 ms 85312 KB Output is correct
60 Correct 910 ms 84108 KB Output is correct
61 Correct 1084 ms 82432 KB Output is correct
62 Correct 1035 ms 83916 KB Output is correct
63 Correct 1000 ms 82836 KB Output is correct
64 Correct 1405 ms 88256 KB Output is correct
65 Correct 314 ms 77400 KB Output is correct
66 Correct 1907 ms 100612 KB Output is correct
67 Correct 1439 ms 111496 KB Output is correct
68 Correct 1342 ms 101828 KB Output is correct
69 Correct 1339 ms 102724 KB Output is correct
70 Correct 2687 ms 125252 KB Output is correct
71 Correct 2128 ms 103412 KB Output is correct
72 Correct 1256 ms 111552 KB Output is correct
73 Correct 1250 ms 102976 KB Output is correct
74 Correct 1308 ms 101404 KB Output is correct
75 Correct 1578 ms 101204 KB Output is correct
76 Correct 1169 ms 99680 KB Output is correct
77 Correct 1212 ms 102080 KB Output is correct
78 Correct 1279 ms 99156 KB Output is correct
79 Correct 1264 ms 100096 KB Output is correct
80 Correct 1428 ms 100160 KB Output is correct
81 Correct 333 ms 64216 KB Output is correct
82 Correct 340 ms 64216 KB Output is correct
83 Correct 331 ms 63200 KB Output is correct
84 Correct 303 ms 63456 KB Output is correct
85 Correct 317 ms 63832 KB Output is correct
86 Correct 298 ms 62952 KB Output is correct
87 Correct 312 ms 63584 KB Output is correct
88 Correct 317 ms 63572 KB Output is correct
89 Correct 305 ms 63200 KB Output is correct
90 Correct 143 ms 62692 KB Output is correct
91 Correct 326 ms 64368 KB Output is correct
92 Correct 331 ms 63572 KB Output is correct
93 Correct 326 ms 63204 KB Output is correct
94 Correct 322 ms 63200 KB Output is correct
95 Correct 305 ms 63200 KB Output is correct
96 Correct 180 ms 62692 KB Output is correct
97 Correct 1887 ms 114332 KB Output is correct
98 Correct 350 ms 82648 KB Output is correct
99 Correct 2215 ms 110280 KB Output is correct
100 Correct 1828 ms 114332 KB Output is correct
101 Correct 1841 ms 111936 KB Output is correct
102 Correct 2268 ms 112068 KB Output is correct
103 Correct 1850 ms 110064 KB Output is correct
104 Correct 2001 ms 110524 KB Output is correct
105 Correct 1645 ms 110148 KB Output is correct
106 Correct 1726 ms 110404 KB Output is correct
107 Correct 1545 ms 110792 KB Output is correct
108 Correct 1581 ms 111944 KB Output is correct
109 Correct 1590 ms 111304 KB Output is correct
110 Correct 1659 ms 111688 KB Output is correct
111 Correct 1661 ms 112072 KB Output is correct
112 Correct 1617 ms 110668 KB Output is correct
113 Correct 591 ms 103744 KB Output is correct
114 Correct 1668 ms 114732 KB Output is correct
115 Correct 1691 ms 111936 KB Output is correct
116 Correct 1681 ms 110936 KB Output is correct
117 Correct 1797 ms 111188 KB Output is correct
118 Correct 1721 ms 110640 KB Output is correct
119 Correct 818 ms 101568 KB Output is correct
120 Correct 1065 ms 109704 KB Output is correct
121 Correct 1157 ms 109380 KB Output is correct
122 Correct 1105 ms 109548 KB Output is correct
123 Correct 1224 ms 109628 KB Output is correct
124 Correct 1330 ms 109780 KB Output is correct
125 Correct 1219 ms 109948 KB Output is correct
126 Correct 1418 ms 112064 KB Output is correct