oj.uz

답안 #233099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233099 2020-05-19T10:50:36 Z nvmdava 새 집 (APIO18_new_home) C++17
0 / 100
 1132 ms 140756 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 1000005
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];
multiset<pair<int, int> > in;
vector<pair<pair<int, int>, pair<int, int> > > lol;
int seg[N];
 
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(){
    lol.clear();
    memset(seg, 0, sizeof seg);
    for(int i = 1; i <= k; ++i){
        in.clear();
        in.insert({INF, 1});
        in.insert({-INF, 1});
        for(auto& x : sh[i]){
            if(x.ss > 0){
                auto r = in.insert({x.ss, x.ff});
                auto l = r++;
                auto it = l--;
                lol.push_back({{(r -> ff + l -> ff) / 2, r -> ff}, {r -> ss, x.ff - 1}});
                in.insert({r -> ff, x.ff});
                in.erase(r);
            } else {
                auto r = in.lower_bound({-x.ss, 0});
                auto l = r++;
                auto it = l--;
                lol.push_back({{(it -> ff + l -> ff) / 2, it -> ff}, {it -> ss, x.ff - 1}});
                lol.push_back({{(it -> ff + r -> ff) / 2, r -> ff}, {r -> ss, x.ff - 1}});
                in.insert({r -> ff, x.ff});
                in.erase(it);
                in.erase(r);
            }
        }
        auto r = in.begin();
        auto l = r++;
        lol.push_back({{(r -> ff + l -> ff) / 2, r -> ff}, {r -> ss, tmp.size()}});
    }
    for(int i = 1; i <= q; ++i)
        lol.push_back({{l[i], 1'000'000'000}, {i, y[i]}});
    
    sort(lol.begin(), lol.end());
    for(auto& x : lol){
        if(x.ff.ss != 1'000'000'000){
            if(x.ss.ff <= x.ss.ss && x.ff.ss > 0){
                update(1, 1, 300'005, x.ss.ff, x.ss.ss, x.ff.ss);
            }
        }
        else
            ans[x.ss.ff] = max(ans[x.ss.ff], query(1, 1, 300'005, 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());
 
    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());
    solve();
 
    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] > 200'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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 27776 KB Output is correct
2 Correct 21 ms 27776 KB Output is correct
3 Correct 21 ms 27776 KB Output is correct
4 Correct 21 ms 27776 KB Output is correct
5 Incorrect 22 ms 27896 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 27776 KB Output is correct
2 Correct 21 ms 27776 KB Output is correct
3 Correct 21 ms 27776 KB Output is correct
4 Correct 21 ms 27776 KB Output is correct
5 Incorrect 22 ms 27896 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1132 ms 90412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 969 ms 140756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 27776 KB Output is correct
2 Correct 21 ms 27776 KB Output is correct
3 Correct 21 ms 27776 KB Output is correct
4 Correct 21 ms 27776 KB Output is correct
5 Incorrect 22 ms 27896 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 27776 KB Output is correct
2 Correct 21 ms 27776 KB Output is correct
3 Correct 21 ms 27776 KB Output is correct
4 Correct 21 ms 27776 KB Output is correct
5 Incorrect 22 ms 27896 KB Output isn't correct
6 Halted 0 ms 0 KB -