Submission #260479

#	Time	Username	Problem	Language	Result	Execution time	Memory
260479		Kastanda	New Home (APIO18_new_home)	C++11	0 / 100	5087 ms	854540 KiB

new_home

// M
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 300005, MXN = N * 3, INF = 1e9 + 9;
struct Data {int l, r, a, b;};
int n, q, k, nwtp, nwtm, X[N], T[N], L[N], R[N], Y[N], Z[N], RS[N];
map < pair < int , int > , vector < tuple < int , int , int > > > MP[N];
vector < pair < int , int > > E;
multiset < int > ST[N];
vector < Data > QD[MXN * 4];
vector < int > U, OP, V[N * 2][2];
inline int GetId(int val)
{
        return (int)(lower_bound(U.begin(), U.end(), val) - U.begin());
}
inline void Adder(int l, int r, int a, int b)
{
        //printf("Adding %d %d :: %d %d ::: %d %d\n", l, r, a, b, nwtp, nwtm);
        MP[nwtp][make_pair(l, r)].push_back(make_tuple(nwtm, a, b));
}
inline void Deler(int l, int r, int a, int b)
{
        //printf("Deleting %d %d :: %d %d ::: %d %d\n", l, r, a, b, nwtp, nwtm);
        MP[nwtp][make_pair(l, r)].push_back(make_tuple(nwtm, 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);
}
void AddSeg(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)
                {
                        if (!V[l][a].size() || V[l][a].back() < b)
                                V[l][a].push_back(b), OP.push_back(l << 1 ^ a);
                        l ++;
                }
                if (r & 1)
                {
                        r --;
                        if (!V[r][a].size() || V[r][a].back() < b)
                                V[r][a].push_back(b), OP.push_back(r << 1 ^ a);
                }
        }
}
pair < int , int > GetSeg(int i)
{
        pair < int , int > rt = {-INF, -INF};
        for (i += (int)U.size(); i; i >>= 1)
        {
                if (V[i][0].size())
                        rt.first = max(rt.first, V[i][0].back());
                if (V[i][1].size())
                        rt.second = max(rt.second, V[i][1].back());
        }
        return rt;
}
void AddQuery(int le, int ri, Data d, int id = 1, int l = 0, int r = (int)E.size())
{
        if (ri <= l || r <= le)
                return ;
        if (le <= l && r <= ri)
                return void(QD[id].push_back(d));
        AddQuery(le, ri, d, lc, l, md);
        AddQuery(le, ri, d, rc, md, r);
}
void DFS(int id = 1, int l = 0, int r = (int)E.size())
{
        OP.push_back(-1);
        for (Data &d : QD[id])
                AddSeg(d.l, d.r, d.a, d.b);//, printf("Adding %d , %d :: %d , %d\n", d.l, d.r, d.a, d.b);
        if (r - l < 2 && E[l].second > 0)
        {
                int i = E[l].second;
                int y = GetId(Y[i]);
                pair < int , int> rt = GetSeg(y);
                RS[i] = max(rt.first - Y[i], rt.second + Y[i]);
                //printf("%d :: %d\n", rt.first, rt.second);
                if (RS[i] > (int)1e8)
                        RS[i] = -1;
                //printf("Answering ...\n");
        }
        if (r - l > 1)
                DFS(lc, l, md), DFS(rc, md, r);
        while (OP.size() && OP.back() != -1)
        {
                // Undo
                int uid = OP.back() >> 1, ua = OP.back() & 1;
                V[uid][ua].pop_back();
                //printf("Deleteing.\n");
                OP.pop_back();
        }
        OP.pop_back();
}
int main()
{
        scanf("%d%d%d", &n, &k, &q);
        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());
        nwtm = -1;
        for (int i = 1; i <= k; i ++)
        {
                nwtp = i;
                ST[i].insert(-INF);
                ST[i].insert(INF);
                Do(-INF, INF);
        }
        for (auto e : E)
        {
                nwtm ++;
                int i = e.second;
                if (i < 0)
                {
                        i = -i;
                        nwtp = T[i];
                        if (e.first == L[i])
                                Add(T[i], X[i]);
                        else
                                Del(T[i], X[i]);
                        continue;
                }
        }

        nwtm ++;
        for (int i = 1; i <= k; i ++)
        {
                ST[i].clear();
                for (auto a : MP[i])
                {
                        int l = a.first.first;
                        int r = a.first.second;
                        l = GetId(l);
                        r = GetId(r);

                        if (l == r)
                                continue;

                        vector < tuple < int , int , int > > &vec = a.second;
                        if (vec.size() & 1)
                                vec.push_back(make_tuple(nwtm, -1, -1));

                        /*printf("=====================\n");
                        printf("%d == %d\n", l, r);
                        for (auto e : vec)
                        {
                                int t, y, z;
                                tie(t, y, z) = e;
                                printf("%d :: %d :: %d\n", t, y, z);
                        }*/

                        for (int j = 0; j < (int)vec.size(); j += 2)
                        {
                                int t1, t2, y, z;
                                tie(t2, y, z) = vec[j + 1];
                                tie(t1, y, z) = vec[j];
                                if (t1 == t2 || t2 <= 0)
                                        continue;
                                //printf("Time [%d, %d] : %d , %d , %d , %d\n", t1, t2, l, r, y, z);
                                AddQuery(t1, t2, Data {l, r, y, z});
                        }
                }
        }
        DFS();



        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:142: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:145: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:151: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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20