Submission #389858

#	Time	Username	Problem	Language	Result	Execution time	Memory
389858		phathnv	New Home (APIO18_new_home)	C++11	0 / 100	5105 ms	101256 KiB

new_home

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

template<typename T>
void read(T &x){
    char ch;
    for(ch = getchar(); !isdigit(ch); ch = getchar());
    x = ch - '0';
    for(ch = getchar(); isdigit(ch); ch = getchar())
        x = x * 10 + ch - '0';
}

template<typename T>
void write(T x){
    if (x < 0){
        putchar('-');
        write(-x);
        return;
    }
    if (x < 10){
        putchar(x + '0');
    } else {
        write(x / 10);
        putchar(x % 10 + '0');
    }
}

const int N = 3e5 + 10;
const int INF = 4e8 + 10;

struct segment{
    int type, x, y, a, b;
    segment(int _type = 0, int _x = 0, int _y = 0, int _a = 0, int _b = 0){
        type = _type;
        x = _x;
        y = _y;
        a = _a;
        b = _b;
    }
    bool operator < (const segment &other){
        if (type != other.type)
            return type < other.type;
        if (x != other.x)
            return x < other.x;
        return y < other.y;
    }
};

struct query{
    int x, t, id;
    bool operator < (const query &other){
        return x < other.x;
    }
};

struct node{
    int x, id, idL, idR;
    node(int _x = 0, int _id = 0, int _idL = 0, int _idR = 0){
        x = _x;
        id = _id;
        idL = _idL;
        idR = _idR;
    }
};

bool operator < (const node &a, const node &b){
    if (a.x != b.x)
        return a.x < b.x;
    if (a.id != b.id)
        return a.id < b.id;
    if (a.idL != b.idL)
        return a.idL < b.idL;
    return a.idR < b.idR;
}

struct event{
    int t, type, id;
    event(int _t = 0, int _type = 0, int _id = 0){
        t = _t;
        type = _type;
        id = _id;
    }
    bool operator < (const event &other){
        if (t != other.t)
            return t < other.t;
        if (type != other.type)
            return type < other.type;
        return id < other.id;
    }
};

int n, k, nQ;
int x[N], t[N], a[N], b[N], ans[N];
query q[N];

int nSeg, nE;
segment seg[10 * N];
event e[N * 2];

int nTQ, tQ[N];

void readInput(){
    read(n);
    read(k);
    read(nQ);
    for(int i = 1; i <= n; i++){
        read(x[i]);
        read(t[i]);
        read(a[i]);
        read(b[i]);
    }
    for(int i = 1; i <= nQ; i++){
        read(q[i].x);
        read(q[i].t);
        q[i].id = i;
    }
}

void updateSeg(node &l, node &r, int a){
    int mid = (l.x + r.x) >> 1;
    seg[++nSeg] = segment(1, mid, mid - l.x, a, -1);
    if (l.idR != -1)
        seg[l.idR].b = a - 1;
    l.idR = nSeg;

    seg[++nSeg] = segment(-1, mid, r.x - mid, a, -1);
    if (r.idL != -1)
        seg[r.idL].b = a - 1;
    r.idL = nSeg;
}

vector <int> type[N];
void init(){
    for(int i = 1; i <= n; i++)
        x[i] <<= 1;
    for(int i = 1; i <= nQ; i++)
        q[i].x <<= 1;

    for(int i = 1; i <= n; i++)
        type[t[i]].push_back(i);

    for(int typ = 1; typ <= k; typ++){
        nE = 0;
        for(int pos : type[typ]){
            e[++nE] = event(a[pos], 1, pos);
            e[++nE] = event(b[pos] + 1, -1, pos);
        }
        sort(e + 1, e + 1 + nE);

        set <node> S;
        node l(-INF, -1, -1, -1), r(INF, -1, -1, -1);
        updateSeg(l, r, 0);
        S.insert(l);
        S.insert(r);
        for(int i = 1; i <= nE; i++){
            if (e[i].type == -1){
                auto it = S.lower_bound(node(x[e[i].id], e[i].id, -1, -1));
                auto itL = S.end(), itR = S.end();
                if (it != S.end()){
                    itR = it;
                    ++itR;
                }
                if (it != S.begin()){
                    itL = it;
                    --itL;
                }
                node d = *it;
                if (d.idL != -1)
                    seg[d.idL].b = e[i].t - 1;
                if (d.idR != -1)
                    seg[d.idR].b = e[i].t - 1;
                S.erase(it);

                if (itL != S.end() && itR != S.end()){
                    node nL = *itL, nR = *itR;
                    S.erase(itL);
                    S.erase(itR);
                    updateSeg(nL, nR, e[i].t);
                    S.insert(nL);
                    S.insert(nR);
                }

            } else {
                auto it = S.lower_bound(node(x[e[i].id], e[i].id, -1, -1));
                auto itR = it, itL = S.end();
                if (itR != S.begin()){
                    itL = itR;
                    --itL;
                }
                node d = node(x[e[i].id], e[i].id, -1, -1);
                if (itL != S.end()){
                    node nL = *itL;
                    S.erase(itL);
                    updateSeg(nL, d, e[i].t);
                    S.insert(nL);
                }
                if (itR != S.end()){
                    node nR = *itR;
                    S.erase(itR);
                    updateSeg(d, nR, e[i].t);
                    S.insert(nR);
                }
                S.insert(d);
            }
        }

        node nL = *S.begin(), nR = *(++S.begin());
        seg[nL.idR].b = INF;
        seg[nR.idL].b = INF;
    }
}

struct segmentTree{
    vector <int> d[N * 4];
    int cnt[N * 4], cur[N * 4];

    void fakeAddSeg(int id, int l, int r, int u, int v){
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            cnt[id]++;
            return;
        }
        int mid = (l + r) >> 1;
        fakeAddSeg(id << 1, l, mid, u, v);
        fakeAddSeg(id << 1 | 1, mid + 1, r, u, v);
    }
    void normalize(int id, int l, int r){
        d[id].resize(cnt[id]);
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        normalize(id << 1, l, mid);
        normalize(id << 1 | 1, mid + 1, r);
    }
    void addSeg(int id, int l, int r, int u, int v, int pos){
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            d[id][cur[id]++] = pos;
            return;
        }
        int mid = (l + r) >> 1;
        addSeg(id << 1, l, mid, u, v, pos);
        addSeg(id << 1 | 1, mid + 1, r, u, v, pos);
    }
    void solve(int id, int l, int r, vector<query> &curQ){
        if (curQ.empty())
            return;

        auto ptr1 = d[id].begin();
        int maxVal = -INF;
        for(auto ptrQ = curQ.begin(); ptrQ != curQ.end(); ++ptrQ){
            while (ptr1 != d[id].end() && seg[*ptr1].type == -1 && seg[*ptr1].x <= ptrQ -> x){
                maxVal = max(maxVal, seg[*ptr1].x + seg[*ptr1].y);
                ++ptr1;
            }
            ans[ptrQ -> id] = max(ans[ptrQ -> id], maxVal - ptrQ -> x);
        }

        auto ptr2 = d[id].rbegin();
        maxVal = -INF;
        for(auto ptrQ = curQ.rbegin(); ptrQ != curQ.rend(); ++ptrQ){
            while (ptr2 != d[id].rend() && seg[*ptr2].type == 1 && seg[*ptr2].x >= ptrQ -> x){
                maxVal = max(maxVal, seg[*ptr2].y - seg[*ptr2].x);
                ++ptr2;
            }
            ans[ptrQ -> id] = max(ans[ptrQ -> id], maxVal + ptrQ -> x);
        }

        if (l == r)
            return;

        int mid = (l + r) >> 1;
        vector <query> lQ, rQ;
            for(query q : curQ)
                if (q.t <= mid)
                    lQ.push_back(q);
                else
                    rQ.push_back(q);

        solve(id << 1, l, mid, lQ);
        solve(id << 1 | 1, mid + 1, r, rQ);
    }
} ST;

void solve(){
    sort(seg + 1, seg + 1 + nSeg);
    sort(q + 1, q + 1 + nQ);
    nTQ = 0;
    for(int i = 1; i <= nQ; i++)
        tQ[++nTQ] = q[i].t;
    sort(tQ + 1, tQ + 1 + nTQ);
    nTQ = unique(tQ + 1, tQ + 1 + nTQ) - (tQ + 1);
    for(int i = 1; i <= nQ; i++)
        q[i].t = lower_bound(tQ + 1, tQ + 1 + nTQ, q[i].t) - tQ;
    for(int i = 1; i <= nSeg; i++){
        seg[i].a = lower_bound(tQ + 1, tQ + 1 + nTQ, seg[i].a) - tQ;
        seg[i].b = upper_bound(tQ + 1, tQ + 1 + nTQ, seg[i].b) - tQ - 1;
        if (seg[i].a <= seg[i].b)
            ST.fakeAddSeg(1, 1, nTQ, seg[i].a, seg[i].b);
    }
    ST.normalize(1, 1, nTQ);
    for(int i = 1; i <= nSeg; i++)
        if (seg[i].a <= seg[i].b)
            ST.addSeg(1, 1, nTQ, seg[i].a, seg[i].b, i);
    vector <query> curQ;
    for(int i = 1; i <= nQ; i++)
        curQ.push_back(q[i]);
    ST.solve(1, 1, nTQ, curQ);

    for(int i = 1; i <= nQ; i++){
        write(ans[i] >= (INF >> 1)? -1 : (ans[i] >> 1));
        putchar('\n');
    }
}

int main(){
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    readInput();
    init();
    solve();
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:327:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  327 |     freopen("inp.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:328:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  328 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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