Submission #259709

#	Time	Username	Problem	Language	Result	Execution time	Memory
259709		Kastanda	New Home (APIO18_new_home)	C++11	47 / 100	5086 ms	293192 KiB

new_home

// M
#include<bits/stdc++.h>
using namespace std;
const int N = 300005, INF = 1e9 + 9;
int n, q, k, X[N], T[N], L[N], R[N], Y[N], Z[N], RS[N];
vector < int > U;
multiset < int > ST[N];
struct Set {
        priority_queue < int > PQ, DL;
        inline void Insert(int val) {
                PQ.push(val);
        }
        inline void Delete(int val) {
                DL.push(val);
        }
        inline int GetMax() {
                while (DL.size() && DL.top() == PQ.top())
                        DL.pop(), PQ.pop();
                return PQ.size() ? PQ.top() : INT_MIN;
        }
};
Set D[N * 2][2];
inline int GetId(int val)
{
        return (int)(lower_bound(U.begin(), U.end(), val) - U.begin());
}
inline void Add(int l, int r, int a, int b)
{
        l += (int)U.size();
        r += (int)U.size();
        for (; l < r; l >>= 1, r >>= 1)
        {
                if (l & 1) D[l][a].Insert(b), l ++;
                if (r & 1) r --, D[r][a].Insert(b);
        }
}
inline void Del(int l, int r, int a, int b)
{
        l += (int)U.size();
        r += (int)U.size();
        for (; l < r; l >>= 1, r >>= 1)
        {
                if (l & 1) D[l][a].Delete(b), l ++;
                if (r & 1) r --, D[r][a].Delete(b);
        }
}
inline pair < int , int > Get(int i)
{
        pair < int , int > rt = {-INF, -INF};
        for (i += (int)U.size(); i; i >>= 1)
        {
                rt.first = max(rt.first, D[i][0].GetMax());
                rt.second = max(rt.second, D[i][1].GetMax());
        }
        return rt;
}
inline void Adder(int l, int r, int a, int b)
{
        l = GetId(l);
        r = GetId(r);
        Add(l, r, a, b);
}
inline void Deler(int l, int r, int a, int b)
{
        l = GetId(l);
        r = GetId(r);
        Del(l, r, a, b);
}
inline void Do(int l, int r)
{
        int mid = (l + r + 1) >> 1;
        // [l, mid)
        Adder(l, mid, 1, -l);
        // [mid, r]
        Adder(mid, r + 1, 0, r);
}
inline void Undo(int l, int r)
{
        int mid = (l + r + 1) >> 1;
        // [l, mid)
        Deler(l, mid, 1, -l);
        // [mid, r]
        Deler(mid, r + 1, 0, r);
}
inline void Add(int tp, int x)
{
        auto it = ST[tp].lower_bound(x);
        assert(it != ST[tp].end());
        if (* it == x)
                return void(ST[tp].insert(x));
        int r = * it; it --;
        int l = * it;
        Undo(l, r);
        Do(l, x);
        Do(x, r);
        ST[tp].insert(x);
}
inline void Del(int tp, int x)
{
        auto it = ST[tp].lower_bound(x);
        assert(* it == x);
        it = ST[tp].erase(it);
        if (* it == x)
                return ;
        int r = * it; it --;
        int l = * it;
        Undo(l, x);
        Undo(x, r);
        Do(l, r);
}
int main()
{
        scanf("%d%d%d", &n, &k, &q);
        vector < pair < int , int > > E;
        for (int i = 1; i <= n; i ++)
        {
                scanf("%d%d%d%d", &X[i], &T[i], &L[i], &R[i]);
                E.push_back({L[i], -i});
                E.push_back({R[i] + 1, -i});
        }
        for (int i = 1; i <= q; i ++)
        {
                scanf("%d%d", &Y[i], &Z[i]);
                E.push_back({Z[i], i});
                U.push_back(Y[i]);
        }
        sort(E.begin(), E.end());
        sort(U.begin(), U.end());
        U.resize(unique(U.begin(), U.end()) - U.begin());
        for (int i = 1; i <= k; i ++)
        {
                ST[i].insert(-INF);
                ST[i].insert(INF);
                Do(-INF, INF);
        }
        for (auto e : E)
        {
                int i = e.second;
                if (i < 0)
                {
                        i = -i;
                        if (e.first == L[i])
                                Add(T[i], X[i]);
                        else
                                Del(T[i], X[i]);
                        continue;
                }
                int y = GetId(Y[i]);
                pair < int , int> rt = Get(y);
                RS[i] = max(rt.first - Y[i], rt.second + Y[i]);
                if (RS[i] > (int)1e8)
                        RS[i] = -1;
        }
        for (int i = 1; i <= q; i ++)
                printf("%d\n", RS[i]);
        return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &n, &k, &q);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:117:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d%d%d", &X[i], &T[i], &L[i], &R[i]);
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:123:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d", &Y[i], &Z[i]);
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20