Submission #728996

#	Time	Username	Problem	Language	Result	Execution time	Memory
728996		DeMen100ns	New Home (APIO18_new_home)	C++17	100 / 100	2266 ms	125064 KiB

new_home

#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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20