oj.uz

Submission #161011

# Submission time Handle Problem Language Result Execution time Memory
161011 2019-10-31T08:00:02 Z Minnakhmetov New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 381464 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;
};
 
struct U {
    int l, r;
    pair<int, int> p;
};
 
const int N = 3e5 + 5, INF = 1e9, MAX = 1e8;
int n, q, k, cq;
int ans[N];
pair<int, int> lt[N], tmp[N];
unordered_map<int, vector<int>> mp[2][N];
 
vector<int> vx;
multiset<int> occ[N];
vector<pair<int, int>> t[N * 4];
vector<U> updates[2];
 
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 type, int x, int y) {
    mp[type][x][y].push_back(cq);
}
 
void endSeg(int type, int x, int y) {
    updates[type].push_back({mp[type][x][y].back(), cq - 1, {x, y}});
    mp[type][x][y].pop_back();
}
 
void updBeg(int x, bool add) {
    if (add)
        startSeg(0, 0, x);
    else
        endSeg(0, 0, x);
}
 
void updBetween(int x, int y, bool add) {
    if (x == y)
        return;
    int m = (x + y) / 2;
    if ((x + y) % 2)
        m++;
 
    int m1 = lower_bound(all(vx), m) - vx.begin();
    if (add) {
        // if (x == 1) {
        //     for (int i : vx) {
        //         cout << i << " ";
        //     }
        //     cout << "\n";
        //     cout << x << " " << y << " " << m1 << " " << q - m1 << "\n";
        // }
        startSeg(0, m1, y);
        startSeg(1, q - m1, INF - x);
    }
    else {
        endSeg(0, m1, y);
        endSeg(1, q - m1, INF - x);
    }
}

void updEnd(int x, bool add) {
    if (add)
        startSeg(1, 0, INF - x);
    else
        endSeg(1, 0, INF - x);
}
 
void calcAns(int v, int L, int R) {
    if (L != R) {
        int m = (L + R) >> 1;
        calcAns(v * 2, L, m);
        calcAns(v * 2 + 1, m + 1, R);
        
        int x = L, y = m + 1, z = 0;
        while (x <= m || y <= R) {
            if (x <= m && (y == R + 1 || lt[x].first < lt[y].first))
                tmp[z] = lt[x++];
            else 
                tmp[z] = lt[y++];
            z++;
        }
        for (int i = L; i <= R; i++)
            lt[i] = tmp[i - L];
    }
 
    int i = 0, mx = -INF;
    for (int j = L; j <= R; j++) {
        while (i < t[v].size() && t[v][i].first <= lt[j].first) {
            mx = max(mx, t[v][i].second);
            i++;
        }
        ans[lt[j].second] = max(ans[lt[j].second], mx - vx[lt[j].first]);
    }
}
 
void calcUpdates(vector<E> evs) { 
    for (E e : evs) {
        if (e.t == 2)
            vx.push_back(e.x);
    }
 
    sort(all(vx));
    vx.erase(unique(all(vx)), vx.end());
 
    cq = 0;
 
    for (E e : evs) {
        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);
                }
                if (it == occ[e.y].end()) {
                    updEnd(*prev(it), false);
                }
            }
 
            it = occ[e.y].insert(e.x);
 
            if (it == occ[e.y].begin()) 
                updBeg(e.x, true);
            else
                updBetween(*prev(it), e.x, true);
 
            if (next(it) != occ[e.y].end())
                updBetween(e.x, *next(it), true);
            else
                updEnd(e.x, 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);
            else
                updEnd(e.x, 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);

            if (next(it) == occ[e.y].end() &&
                occ[e.y].size() > 1)
                updEnd(*prev(it), true);
 
            occ[e.y].erase(it);
        }
        else {
            cq++;
        }
    }

    for (int i = 0; i < 2; i++) {
        sort(all(updates[i]), [](const U &a, const U &b) {
            return a.p.first < b.p.first;
        });
    }
}

void solve(vector<U> updates, vector<E> evs) {
    for (int i = 0; i < N * 4; i++)
        t[i].clear();

    cq = 0;

    for (E &e : evs) {
        if (e.t == 2) {
            lt[cq++] = {lower_bound(all(vx), e.x) - vx.begin(), e.y};
        }
    }

    for (U u : updates) {
        upd(u.l, u.r, u.p, 1, 0, q - 1);
    }

    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});
    }
 
    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;
    });

    calcUpdates(evs);
    solve(updates[0], evs);

    for (E &e : evs)
        e.x = INF - e.x;
    for (int &x : vx)
        x = INF - x;
    reverse(all(vx));

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

Compilation message

new_home.cpp: In function 'void calcAns(int, int, int)':
new_home.cpp:109:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i < t[v].size() && t[v][i].first <= lt[j].first) {
                ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 75512 KB Output is correct
2 Correct 90 ms 75512 KB Output is correct
3 Correct 88 ms 75640 KB Output is correct
4 Correct 87 ms 75512 KB Output is correct
5 Incorrect 93 ms 75640 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 75512 KB Output is correct
2 Correct 90 ms 75512 KB Output is correct
3 Correct 88 ms 75640 KB Output is correct
4 Correct 87 ms 75512 KB Output is correct
5 Incorrect 93 ms 75640 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3888 ms 277980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 75512 KB Output is correct
2 Correct 90 ms 75512 KB Output is correct
3 Correct 88 ms 75640 KB Output is correct
4 Correct 87 ms 75512 KB Output is correct
5 Incorrect 93 ms 75640 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 75512 KB Output is correct
2 Correct 90 ms 75512 KB Output is correct
3 Correct 88 ms 75640 KB Output is correct
4 Correct 87 ms 75512 KB Output is correct
5 Incorrect 93 ms 75640 KB Output isn't correct
6 Halted 0 ms 0 KB -