oj.uz

Submission #1100172

# Submission time Handle Problem Language Result Execution time Memory
1100172 2024-10-13T08:30:36 Z vladilius New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 87140 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e8;

struct IT{
    vector<pii> all;
    void add(int l, int r){
        all.pb({l, r});
    }
    void rem(int l, int r){
        for (int i = 0; i < all.size(); i++){
            if (all[i].ff == l && all[i].ss == r){
                all.erase(all.begin() + i);
                return;
            }
        }
    }
    bool get(int l, int r){
        for (auto [x, y]: all){
            if (x <= l && r <= y){
                return 1;
            }
        }
        return 0;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k, q; cin>>n>>k>>q;
    vector<int> x(n + 1), t(n + 1), a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>x[i]>>t[i]>>a[i]>>b[i];
    }
    vector<int> xq(q + 1), yq(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>xq[i]>>yq[i];
    }

    map<int, vector<pii>> mp;
    for (int i = 1; i <= n; i++){
        mp[a[i]].pb({1, i});
        mp[b[i] + 1].pb({2, i});
    }
    for (int i = 1; i <= q; i++){
        mp[yq[i]].pb({i + 2, xq[i]});
    }
    
    vector<int> out(q + 1), cnt(k + 1);
    multiset<int> st[k + 1];
    int df = 0, l, r;
    vector<pii> qq;
    IT T; 
    for (auto [X, V]: mp){
        qq.clear();
        for (auto [tt, i]: V){
            if (tt == 1){
                df += !cnt[t[i]];
                cnt[t[i]]++;
                if (st[t[i]].empty()){
                    if (1 < x[i]) T.add(1, x[i] - 1);
                    if (x[i] < inf) T.add(x[i] + 1, inf);
                    st[t[i]].insert(x[i]);
                    continue;
                }
                
                if (st[t[i]].find(x[i]) != st[t[i]].end()){
                    st[t[i]].insert(x[i]);
                    continue;
                }
                
                auto it = st[t[i]].upper_bound(x[i]);
                if (it == st[t[i]].end()) r = inf;
                else r = (*it) - 1;
                if (it == st[t[i]].begin()) l = 1;
                else l = *prev(it) + 1;
                
                if (l <= r) T.rem(l, r);
                if (l < x[i]) T.add(l, x[i] - 1);
                if (x[i] < r) T.add(x[i] + 1, r);
                
                st[t[i]].insert(x[i]);
            }
            else if (tt == 2){
                cnt[t[i]]--;
                df -= !cnt[t[i]];
                
                if (st[t[i]].count(x[i]) > 1){
                    st[t[i]].erase(st[t[i]].find(x[i]));
                    continue;
                }
                
                auto it = st[t[i]].find(x[i]);
                
                if (it == st[t[i]].begin()) l = 1;
                else l = *prev(it) + 1;
                if (it == prev(st[t[i]].end())) r = inf;
                else r = *next(it) - 1;
                
                if (l < x[i]) T.rem(l, x[i] - 1);
                if (x[i] < r) T.rem(x[i] + 1, r);
                
                if (cnt[t[i]]) T.add(l, r);
                st[t[i]].erase(it);
            }
            else {
                qq.pb({tt - 2, i});
            }
        }
        for (auto [ii, x]: qq){
            if (df < k){
                out[ii] = -1;
                continue;
            }
            
            auto check = [&](int d){
                return T.get(max(1, x - d), min(inf, x + d));
            };
            
            int l = 0, r = inf;
            while (l + 1 < r){
                int m = (l + r) / 2;
                if (check(m)){
                    l = m + 1;
                }
                else {
                    r = m;
                }
            }
            if (check(l)) l = r;
            
            out[ii] = l;
        }
    }
    
    for (int i = 1; i <= q; i++){
        cout<<out[i]<<"\n";
    }
}

Compilation message

new_home.cpp: In member function 'void IT::rem(int, int)':
new_home.cpp:16:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for (int i = 0; i < all.size(); i++){
      |                         ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 608 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 484 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 4 ms 596 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 4 ms 472 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 3 ms 596 KB Output is correct
23 Correct 3 ms 596 KB Output is correct
24 Correct 3 ms 644 KB Output is correct
25 Correct 4 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 464 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 472 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 608 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 484 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 4 ms 596 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 4 ms 472 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 3 ms 596 KB Output is correct
23 Correct 3 ms 596 KB Output is correct
24 Correct 3 ms 644 KB Output is correct
25 Correct 4 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 464 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 472 KB Output is correct
31 Execution timed out 5054 ms 25992 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5065 ms 61136 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 5058 ms 87140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 608 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 484 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 4 ms 596 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 4 ms 472 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 3 ms 596 KB Output is correct
23 Correct 3 ms 596 KB Output is correct
24 Correct 3 ms 644 KB Output is correct
25 Correct 4 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 464 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 472 KB Output is correct
31 Execution timed out 5054 ms 25992 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 608 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 484 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 4 ms 596 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 4 ms 472 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 3 ms 596 KB Output is correct
23 Correct 3 ms 596 KB Output is correct
24 Correct 3 ms 644 KB Output is correct
25 Correct 4 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 464 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 472 KB Output is correct
31 Execution timed out 5054 ms 25992 KB Time limit exceeded
32 Halted 0 ms 0 KB -