oj.uz

Submission #952286

# Submission time Handle Problem Language Result Execution time Memory
952286 2024-03-23T13:43:13 Z Itamar New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 629556 KB 
#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define pd pair<double,double>

const int siz = 3e5 + 2;
multiset<int> col[siz];
int K;
struct node {
    int l, r, mid, maxi;
    bool p;
    multiset<int> s;
    node* sl = NULL;
    node *sr = NULL;
    node(int li, int ri) {
        l = li, r = ri, mid = (l + r) / 2, maxi = 0;
        if (l == 0) {
            maxi = 3e8 + 1;

            if (r == 0) {
                for (int i = 0; i < K; i++)s.insert(3e8 + 1);
            }
            else open();
        }
    }
    void open() {
        
        if (sl == NULL && (l < r)) {
            p = 1;
            sl = new node(l, mid);
            sr = new node(mid + 1, r);
        }
    }
    int query(int a, int b) {
        if (a > r || b < l)return 0;
        if (a <= l && b >= r)return maxi;
        if (p)return max(sl->query(a, b), sr->query(a, b));
        return 0;
    }
    void update(int v, int x, bool f) {
        if (l == r) {
            if (f)s.insert(v);
            else s.erase(s.find(v));
            if (s.size())maxi = *(--s.end());
            else maxi = 0;
        }
        else {
            if (sl == NULL)open();
            if (x <= mid) {
                sl->update(v, x, f);
            }
            else {
                sr->update(v, x, f);
            }
            maxi = max(sl->maxi, sr->maxi);
        }
    }
};
map<pi, int> sum;
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, k, q;
    cin >> n >> k >> q;
    vector<vi> ev;
    K = k;
    for (int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        x++;
        ev.push_back({ a,1,x,t });
        ev.push_back({b+1,0,x,t });
    }
    for (int i = 0; i < siz; i++) {
        col[i].insert(0);
        col[i].insert(3e8 + 1);
    }
    for (int i = 0; i < q; i++) {
        int l, y;
        cin >> l >> y;
        l++;
        ev.push_back({ y,l,i });
    }
    sort(ev.begin(), ev.end());
    node* seg = new node(0, 3e8 + 3);
    vi ans(q);
    for (vi v : ev) {
        if (v.size() == 3) {
            int l = v[1];
            int a = 0, b = 1e8 + 3;
            while (a < b) {
                int mid = (a + b) / 2;
                int ans = seg->query(0, max(l - mid - 1, 0));
                if (ans <= mid + l) {
                    b = mid;
                }
                else {
                    a = mid+1;
                }
            }
            if (b == 1e8 + 3)ans[v[2]] = -1;
            else ans[v[2]] = b;
        }
        else {
            int x = v[2], t = v[3];
            if (v[1])sum[{x, t}]++;
            else sum[{x,t}]--;
            if (v[1] == sum[{x,t}]) {
                auto it = col[t].lower_bound(x);
                auto it1 = it, it2 = it;
                it1--; if (v[1] == 0)it2++;
                if (v[1] == 0)col[t].erase(x);
                else col[t].insert(x);

                seg->update(*it2, x, v[1]);
                seg->update(*it2, *it1, !v[1]);
                seg->update(x, *it1, v[1]);
            }
        }
    }
    for (int i = 0; i < q; i++)cout << ans[i] << "\n";
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 42684 KB Output is correct
2 Correct 31 ms 42844 KB Output is correct
3 Correct 33 ms 42544 KB Output is correct
4 Correct 31 ms 42588 KB Output is correct
5 Correct 33 ms 42592 KB Output is correct
6 Runtime error 66 ms 86488 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 42684 KB Output is correct
2 Correct 31 ms 42844 KB Output is correct
3 Correct 33 ms 42544 KB Output is correct
4 Correct 31 ms 42588 KB Output is correct
5 Correct 33 ms 42592 KB Output is correct
6 Runtime error 66 ms 86488 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3631 ms 629208 KB Output is correct
2 Execution timed out 5035 ms 629556 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 42684 KB Output is correct
2 Correct 31 ms 42844 KB Output is correct
3 Correct 33 ms 42544 KB Output is correct
4 Correct 31 ms 42588 KB Output is correct
5 Correct 33 ms 42592 KB Output is correct
6 Runtime error 66 ms 86488 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 42684 KB Output is correct
2 Correct 31 ms 42844 KB Output is correct
3 Correct 33 ms 42544 KB Output is correct
4 Correct 31 ms 42588 KB Output is correct
5 Correct 33 ms 42592 KB Output is correct
6 Runtime error 66 ms 86488 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -