oj.uz

Submission #160947

# Submission time Handle Problem Language Result Execution time Memory
160947 2019-10-30T16:57:39 Z Minnakhmetov New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 336944 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
  
using namespace std;

struct E {
    int p, t, x, y;
};

const int N = 3e5 + 5, INF = 1e9, MAX = 1e8;
int n, q, k, cc, cq;
int ans[N], ord[N], loc[N], num[N];

vector<int> vx;
multiset<int> occ[N];
map<pair<int, int>, vector<int>> mp;
vector<pair<int, int>> t[N * 4];

struct ST {
    vector<int> t[N * 4];

    void upd(int l, int r, int x, int v, int L, int R) {
        if (l > r)
            return;
        if (l == L && r == R) {
            t[v].push_back(max(t[v].back(), x));
        }
        else {
            int m = (L + R) >> 1;
            upd(l, min(m, r), x, v * 2, L, m);
            upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R);
        }
    }

    void del(int l, int r, int v, int L, int R) {
        if (l > r)
            return;
        if (l == L && r == R) {
            t[v].pop_back();
        }
        else {
            int m = (L + R) >> 1;
            del(l, min(m, r), v * 2, L, m);
            del(max(m + 1, l), r, v * 2 + 1, m + 1, R);
        }
    }

    int que(int x, int v, int L, int R, int ans = -INF) {
        ans = max(ans, t[v].back());
        if (L == R)
            return ans;
        int m = (L + R) >> 1;
        if (x <= m)
            return que(x, v * 2, L, m, ans);
        return que(x, v * 2 + 1, m + 1, R, ans);
    }

    void clear() {
        for (int i = 0; i < N * 4; i++) {
            t[i] = {-INF};
        }
    }
} segt;

void upd(int l, int r, pair<int, int> p, int v, int L, int R) {
    if (l > r)
        return;
    if (L == l && R == r) {
        t[v].push_back(p);
    }
    else {
        int m = (L + R) >> 1;
        upd(l, min(m, r), p, v * 2, L, m);
        upd(max(m + 1, l), r, p, v * 2 + 1, m + 1, R);
    }
}

void startSeg(int x, int y) {
    mp[{x, y}].push_back(cq);
}

void endSeg(int x, int y) {
    auto p = make_pair(x, y);
    upd(mp[{x, y}].back(), cq - 1, p, 1, 0, q - 1);
    mp[{x, y}].pop_back();
}

void updBeg(int x, bool add) {
    if (add)
        startSeg(0, x);
    else
        endSeg(0, x);
}

void updBetween(int x, int y, bool add) {
    if (x == y)
        return;
    int m1 = upper_bound(all(vx), (x + y) >> 1) - vx.begin();
    if (add)
        startSeg(m1, y);
    else
        endSeg(m1, y);
}

void calcAns(int v, int L, int R) {
    for (auto &p : t[v]) {
        segt.upd(p.first, cc - 1, p.second, 1, 0, cc - 1);
    }

    if (L == R) {
        ans[num[L]] = max(ans[num[L]], segt.que(loc[L], 1, 0, cc - 1) - vx[loc[L]]);
    }
    else {
        int m = (L + R) >> 1;
        calcAns(v * 2, L, m);
        calcAns(v * 2 + 1, m + 1, R);
    }

    for (auto &p : t[v]) {
        segt.del(p.first, cc - 1, 1, 0, cc - 1);
    }
}

void solve(vector<E> evs) {
    vx.clear();
    mp.clear();
    for (int i = 0; i < N; i++) {
        occ[i].clear();
        t[i].clear();
    }

    for (E e : evs) {
        if (e.t == 2)
            vx.push_back(e.x);
    }

    sort(all(vx));
    vx.erase(unique(all(vx)), vx.end());

    cc = vx.size();
    cq = 0;

    for (E e : evs) {
        // cout << e.p << " " << e.t << " " << e.x << " " << e.y << "\n";
        if (e.t == 0) {
            auto it = occ[e.y].upper_bound(e.x);
            if (!occ[e.y].empty()) {
                if (it != occ[e.y].begin() && it != occ[e.y].end()) {
                    updBetween(*prev(it), *it, false);
                }
                if (it == occ[e.y].begin()) {
                    updBeg(*it, false);
                }
            }

            it = occ[e.y].insert(e.x);

            if (it == occ[e.y].begin()) 
                updBeg(*it, true);
            else
                updBetween(*prev(it), *it, true);

            if (next(it) != occ[e.y].end())
                updBetween(*it, *next(it), true);

        }
        else if (e.t == 1) {
            auto it = occ[e.y].find(e.x);

            if (it == occ[e.y].begin()) 
                updBeg(*it, false);
            else
                updBetween(*prev(it), *it, false);

            if (next(it) != occ[e.y].end())
                updBetween(*it, *next(it), false);

            if (it != occ[e.y].begin() && next(it) != occ[e.y].end())
                updBetween(*prev(it), *next(it), true);
            if (it == occ[e.y].begin() && occ[e.y].size() > 1)
                updBeg(*next(it), true);

            occ[e.y].erase(it);
        }
        else {
            loc[cq] = lower_bound(all(vx), e.x) - vx.begin();
            num[cq] = e.y;
            cq++;
        }
    }

    segt.clear();
    calcAns(1, 0, q - 1);


}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> k >> q;

    vector<E> evs;

    for (int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        t--;
        evs.push_back({a, 0, x, t});
        evs.push_back({b + 1, 1, x, t});
        vx.push_back(x);
    }

    for (int i = 0; i < k; i++) {
        evs.push_back({1, 0, INF, i});
        evs.push_back({MAX, 1, INF, i});
    }

    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        evs.push_back({y, 2, x, i});
    }

    sort(all(evs), [](const E &a, const E &b) {
        return a.p == b.p ? a.t < b.t : a.p < b.p;
    });

    solve(evs);
    for (E &e : evs)
        e.x = INF - e.x;
    solve(evs);

    for (int i = 0; i < q; i++) {
        if (ans[i] < INF / 2) {
            cout << ans[i] << "\n";
        }
        else {
            cout << "-1\n";
        }
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 108408 KB Output is correct
2 Correct 157 ms 108556 KB Output is correct
3 Correct 158 ms 108580 KB Output is correct
4 Correct 164 ms 108456 KB Output is correct
5 Incorrect 162 ms 108536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 108408 KB Output is correct
2 Correct 157 ms 108556 KB Output is correct
3 Correct 158 ms 108580 KB Output is correct
4 Correct 164 ms 108456 KB Output is correct
5 Incorrect 162 ms 108536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5116 ms 244988 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 5108 ms 336944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 108408 KB Output is correct
2 Correct 157 ms 108556 KB Output is correct
3 Correct 158 ms 108580 KB Output is correct
4 Correct 164 ms 108456 KB Output is correct
5 Incorrect 162 ms 108536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 108408 KB Output is correct
2 Correct 157 ms 108556 KB Output is correct
3 Correct 158 ms 108580 KB Output is correct
4 Correct 164 ms 108456 KB Output is correct
5 Incorrect 162 ms 108536 KB Output isn't correct
6 Halted 0 ms 0 KB -