oj.uz

Submission #1033436

# Submission time Handle Problem Language Result Execution time Memory
1033436 2024-07-24T20:26:13 Z _8_8_ New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 119952 KB 
#include <bits/stdc++.h>
 
using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 21, MOD = (int)1e9+7;
 
int n,k,q,x[N],t[N],a[N],b[N];
struct Q{
    int tp,y,x,v,id;
};
multiset<int> st[N];
vector<Q> s;
bool cmp(Q l,Q r){
    if(l.y != r.y)
        return l.y < r.y;
    return l.tp < r.tp;
}
multiset<pair<int,int>> cur;
void add(int i,int x){
    // cerr << (int)st[i].size() << "x\n";
    auto it = st[i].lower_bound(x);
    int R = *it,L;
    --it;
    L =*it;
    cur.insert({L+1,x - 1});
    cur.insert({x + 1,R - 1});
    cur.erase(cur.find({L + 1,R - 1}));
    st[i].insert(x);
    // cerr << (int)st[i].size() << "x\n";
}
void del(int i,int x){
    auto it = st[i].lower_bound(x);
    it++;
    int R = *it,L;
    --it;--it;
    L =*it;
    cur.erase(cur.find({L + 1,x - 1}));
    cur.erase(cur.find({x + 1,R - 1}));
    cur.insert({L + 1,R - 1});
    st[i].erase(st[i].find(x));
}
int res[N];
bool ok(int l,int r){
    for(auto [L,R]:cur){
        if(L <= l && R >= r) return false;
    }
    return true;
}
void test() {
    cin >> n >> k >> q;
    for(int i = 1;i <= n;++i){
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        Q f,_f;
        f.y = a[i];f.tp = 0;f.v = t[i];f.x = x[i];
        s.push_back(f);
        _f.y = b[i];_f.tp = 2;_f.v = t[i];_f.x = x[i];
        s.push_back(_f);
    }
    for(int i = 1;i <= q;i++){
        int l,y;
        cin >> l >> y;
        Q a;
        a.tp = 1;
        a.id = i;
        a.x = l;
        a.y = y;
        s.push_back(a);
    }
    sort(s.begin(),s.end(),cmp);
    const int inf = (int)1e9;
    for(int i = 1;i <= k;i++) {
        st[i].insert(0);
        st[i].insert((int)1e9 + 1);
        cur.insert({1,inf});
    }
    for(Q d:s) {
        if(d.tp == 0) {
            // cout << d.v << ' ' << d.x << '\n';
            add(d.v,d.x);
        }else if(d.tp == 2) {
            del(d.v,d.x);
        }else{
            if(cur.find({1,(int)1e9}) != cur.end()) {
                res[d.id] = -1;
                continue;
            }
            // continue;
            int l = -1,r = (int)1e9;
            while(r - l > 1){
                int mid = (l + r) >> 1;
                if(ok(d.x - mid,d.x + mid)){
                    r = mid;
                }else{
                    l = mid;
                }
            }
            res[d.id] = r;
        }
    }
    for(int i = 1;i <= q;++i) {
        cout << res[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47448 KB Output is correct
2 Correct 20 ms 47444 KB Output is correct
3 Correct 20 ms 47452 KB Output is correct
4 Incorrect 20 ms 47456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47448 KB Output is correct
2 Correct 20 ms 47444 KB Output is correct
3 Correct 20 ms 47452 KB Output is correct
4 Incorrect 20 ms 47456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47448 KB Output is correct
2 Correct 20 ms 47444 KB Output is correct
3 Correct 20 ms 47452 KB Output is correct
4 Incorrect 20 ms 47456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47448 KB Output is correct
2 Correct 20 ms 47444 KB Output is correct
3 Correct 20 ms 47452 KB Output is correct
4 Incorrect 20 ms 47456 KB Output isn't correct
5 Halted 0 ms 0 KB -