Submission #513565

#	Time	Username	Problem	Language	Result	Execution time	Memory
513565		blue	New Home (APIO18_new_home)	C++17	47 / 100	5086 ms	375576 KiB

new_home

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using vi = vector<int>;
#define sz(x) int(x.size())


const int mx = 300'000;

int n, k, q;
vi x(1+mx), t(1+mx), a(1+mx), b(1+mx);
vi l(1+mx), y(1+mx);


int get_time(int i)
{
    if(i <= n) return a[i];
    else if(i <= n+q) return y[i-n];
    else return b[i-n-q];
}

bool cmp(int i, int j)
{
    int ti = get_time(i), tj = get_time(j);
    if(ti != tj) return ti < tj;
    else return i < j;
}



const int ss = (1<<20);
const int INF = 2'0000'0000;

vi qlocs;

struct segtree
{
    vi l = vi(ss, 0);
    vi r = vi(ss, 0);
    // vi xpy = vi(ss, -INF);
    // vi xmy = vi(ss, -INF);
    multiset<int>* xpy = new multiset<int>[ss];
    multiset<int>* xmy = new multiset<int>[ss];

    void build(int i, int L, int R)
    {
        // cerr << "build: " << i << ' ' << L << ' ' << R << '\n';
        l[i] = L;
        r[i] = R;
        if(L == R) return;
        build(2*i, L, (L+R)/2);
        build(2*i+1, (L+R)/2+1, R);
    }

    void deploy_xpy(int i, int L, int R, int V)
    {
        if(R < qlocs[l[i]] || qlocs[r[i]] < L || R < L) return;
        else if(L <= qlocs[l[i]] && qlocs[r[i]] <= R)
            xpy[i].insert(V);
        else
        {
            deploy_xpy(2*i, L, R, V);
            deploy_xpy(2*i+1, L, R, V);
        }
    }

    void withdraw_xpy(int i, int L, int R, int V)
    {
        if(R < qlocs[l[i]] || qlocs[r[i]] < L || R < L) return;
        else if(L <= qlocs[l[i]] && qlocs[r[i]] <= R)
            xpy[i].erase(xpy[i].find(V));
        else
        {
            withdraw_xpy(2*i, L, R, V);
            withdraw_xpy(2*i+1, L, R, V);
        }
    }

    void deploy_xmy(int i, int L, int R, int V)
    {
        if(R < qlocs[l[i]] || qlocs[r[i]] < L || R < L) return;
        else if(L <= qlocs[l[i]] && qlocs[r[i]] <= R)
            xmy[i].insert(V);
        else
        {
            deploy_xmy(2*i, L, R, V);
            deploy_xmy(2*i+1, L, R, V);
        }
    }

    void withdraw_xmy(int i, int L, int R, int V)
    {
        if(R < qlocs[l[i]] || qlocs[r[i]] < L || R < L) return;
        else if(L <= qlocs[l[i]] && qlocs[r[i]] <= R)
            xmy[i].erase(xmy[i].find(V));
        else
        {
            withdraw_xmy(2*i, L, R, V);
            withdraw_xmy(2*i+1, L, R, V);
        }
    }

    int solve(int i, int X)
    {
        // cerr << "solve " << i << ' ' << X << '\n';
        int ans = -1;

        if(X < qlocs[l[i]] || qlocs[r[i]] < X) return ans;

        if(qlocs[l[i]] <= X && X <= qlocs[r[i]])
        {
            // cerr << "actually entering\n";





            // for(int ql: qlocs) cerr << "ql = " << ql << '\n';
            // for(int p: xpy[1]) cerr << "xpy = " << p << '\n';
            // for(int mv: xmy[1]) cerr << "xmy = " << mv << '\n';


            if(!xpy[i].empty())
                ans = max(ans, *xpy[i].rbegin() - X);

            if(!xmy[i].empty())
                ans = max(ans, X - *xmy[i].begin());
        }

        if(l[i] != r[i]) ans = max(ans, max(solve(2*i, X), solve(2*i+1, X)));

        return ans;
    }
};

segtree S;

void insert_pair(int u, int v)
{
    int m = (u+v + 1'000'000'000'000LL)/2LL - 500'000'000'000LL;
    // cerr << "insert " << u << ' ' << v << '\n';

    if(u % 2 == v%2)
    {
        S.deploy_xmy(1, u, m-1, u);
        S.deploy_xpy(1, m, v-1, v);
    }
    else
    {
        S.deploy_xmy(1, u, m, u);
        S.deploy_xpy(1, m+1, v, v);
    }
    // S.deploy_xmy(1, u, m-1, u);
    // S.deploy_xpy(1, m, v-1, v);
}

void erase_pair(int u, int v)
{
    int m = (u+v + 1'000'000'000'000LL)/2LL - 500'000'000'000LL;
    // cerr << "erase " << u << ' ' << v << '\n';
    // S.withdraw_xmy(1, u, m-1, u);
    // S.withdraw_xpy(1, m, v-1, v);

    if(u % 2 == v%2)
    {
        S.withdraw_xmy(1, u, m-1, u);
        S.withdraw_xpy(1, m, v-1, v);
    }
    else
    {
        S.withdraw_xmy(1, u, m, u);
        S.withdraw_xpy(1, m+1, v, v);
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++) cin >> x[i] >> t[i] >> a[i] >> b[i];
    for(int j = 1; j <= q; j++) cin >> l[j] >> y[j];

    vi obj;
    for(int i = 1; i <= n; i++)
    {
        obj.push_back(i);
        obj.push_back(n+q+i);
    }

    for(int j = 1; j <= q; j++)
        obj.push_back(n+j);

    sort(obj.begin(), obj.end(), cmp);

    vi ans(1+q, -1);


    set<int> qlocs_set;
    for(int j = 1; j <= q; j++) qlocs_set.insert(l[j]);

    qlocs = vi(1, 0);
    for(int g: qlocs_set) qlocs.push_back(g);

    int Z = sz(qlocs_set);

    // segtree S;
    S.build(1, 1, Z);

    multiset<int> locs[1+k];
    for(int typ = 1; typ <= k; typ++)
    {
        locs[typ].insert(0 - 1*INF);
        locs[typ].insert(INF + 1*INF);

        insert_pair(-INF, 2*INF);
    }

    vi occ(1+k, 0);
    int occ_ct = 0;

    // for(int ql: qlocs) cerr << "ql = " << ql << '\n';
    // for(int p: S.xpy[1]) cerr << "xpy = " << p << '\n';
    // for(int mv: S.xmy[1]) cerr << "xmy = " << mv << '\n';


    for(int o: obj)
    {
        // cerr << "\n\n\n\n\n" << '\n';
        // cerr << "o = " << o << " : " << "time = " << get_time(o) << '\n';
        if(o <= n)
        {
            // cerr << "adding shop " << x[o] << ' ' << t[o] << '\n';
            int shop = o;
            if(occ[t[shop]] == 0) occ_ct++;
            occ[t[shop]]++;

            auto it = locs[t[shop]].lower_bound(x[shop]);
            int next_loc = *it;

            it--;
            int prev_loc = *it;

            erase_pair(prev_loc, next_loc);

            locs[t[shop]].insert(x[shop]);

            insert_pair(prev_loc, x[shop]);
            insert_pair(x[shop], next_loc);

            // for(int p: S.xpy[1]) cerr << "xpy = " << p << '\n';
            // for(int mv: S.xmy[1]) cerr << "xmy = " << mv << '\n';
        }
        else if(o <= n+q)
        {
            int qr = o-n;
            // cerr << "performing query " << qr << '\n';
            if(occ_ct == k) ans[qr] = S.solve(1, l[qr]);
            else ans[qr] = -1;
            // ans[qr] = S.get(l[qr]);
        }
        else
        {
            int shop = o-n-q;

            // cerr << "removing shop " << shop << '\n';

            occ[t[shop]]--;
            if(occ[t[shop]] == 0) occ_ct--;

            locs[t[shop]].erase(locs[t[shop]].find(x[shop]));

            auto it = locs[t[shop]].lower_bound(x[shop]);
            int next_loc = *it;

            it--;
            int prev_loc = *it;

            erase_pair(prev_loc, x[shop]);
            erase_pair(x[shop], next_loc);

            insert_pair(prev_loc, next_loc);
        }
    }

    for(int j = 1; j <= q; j++) cout << ans[j] << '\n';

}

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