Submission #104355

#	Time	Username	Problem	Language	Result	Execution time	Memory
104355		tieunhi	New Home (APIO18_new_home)	C++14	47 / 100	5083 ms	284512 KiB

new_home

#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define maxN 1000000000
#define N 300005
using namespace std;

struct Store {
    int x, type, a, b;
};
struct Query {
    int x, t, id;
    bool operator < (const Query &rhs) const {
        return x < rhs.x;
    }
};
struct Segment {

    int L, R, a, b;
    Segment(int _L=0, int _R=0, int _a=0, int _b=0) : L(_L), R(_R), a(_a), b(_b) {}
};
bool cmpSegLR(Segment p, Segment q) {
    return p.R > q.R || (p.L == q.L && p.L > q.L);
}
bool cmpSegRL(Segment p, Segment q) {
    return p.L < q.L || (p.R == q.R && p.R < q.R);
}

struct SegOnYear {
    vector<int> t[N << 2];
    void update(int l, int r, int id, int x, int y, int val) {
        if (l > y || r < x) return;
        if (l >= x && r <= y) {
            t[id].PB(val);
            return;
        }
        int mid = (r + l)/2;
        update(l, mid, id*2, x, y, val);
        update(mid+1, r, id*2+1, x, y, val);
    }
}tSegLR, tSegRL;
Store sto[N];
Query que[N];
map<pii, int> maLR, maRL;
vector<Segment> segLR, segRL;
int n, k, Q, tMax;
multiset<int> curSet;

vector<pair<int, pii> > allType[N];
int res[N];

int findLef(int x) {
    auto it = curSet.upper_bound(x);
    it--;
    return (*it);
}
int findRig(int x) {
    auto it = curSet.upper_bound(x);
    return (*it);
}
void addSeg(int L, int R, int time) {
    int mid = (R + L)/2;
    maLR[mp(L, mid)] = time;
    maRL[mp(mid, R)] = time;
}
void remSeg(int L, int R, int time) {
    int mid = (R + L)/2;
    if (time >= maLR[mp(L, mid)])
        segLR.PB(Segment(L, mid, maLR[mp(L, mid)], time));
    if (time >= maRL[mp(mid, R)])
        segRL.PB(Segment(mid, R, maRL[mp(mid, R)], time));
}
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
void setup() {
    read(n); read(k); read(Q);

    vector<int> allYear;
    FOR(i, 1, n) {
        read(sto[i].x); read(sto[i].type); read(sto[i].a); read(sto[i].b);
        sto[i].x *= 2;
    }
    FOR(i, 1, Q) {
        read(que[i].x); read(que[i].t); que[i].x *= 2;
        que[i].id = i;
        allYear.PB(que[i].t);
    }
    sort(allYear.begin(), allYear.end());
    allYear.resize(unique(allYear.begin(), allYear.end()) - allYear.begin());
    FOR(i, 1, n) {
        sto[i].a = lower_bound(allYear.begin(), allYear.end(), sto[i].a) - allYear.begin() + 1;
        sto[i].b = upper_bound(allYear.begin(), allYear.end(), sto[i].b) - allYear.begin();
    }
    FOR(i, 1, Q) {
        que[i].t = lower_bound(allYear.begin(), allYear.end(), que[i].t) - allYear.begin() + 1;
    }
    tMax = allYear.size() + 1;
    sort(que+1, que+Q+1);

    FOR(i, 1, n) {
        if (sto[i].a > sto[i].b) continue;
        int type = sto[i].type;
        allType[type].PB(mp(sto[i].a, mp(0, sto[i].x)));
        allType[type].PB(mp(sto[i].b, mp(1, sto[i].x)));
    }
    FOR(i, 1, k) {
        curSet.clear();
        curSet.insert(-maxN); curSet.insert(maxN);
        addSeg(-maxN, maxN, 0);
        sort(allType[i].begin(), allType[i].end());
        for (auto z : allType[i]) {
            int x = z.S.S;
            int time = z.F;
            int type = z.S.F;
            if (type == 0) {
                int L = findLef(x), R = findRig(x);

                remSeg(L, R, time-1);
                addSeg(L, x, time);
                addSeg(x, R, time);
                curSet.insert(x);
            }
            else {
                auto it = curSet.find(x);
                curSet.erase(it);
                int L = findLef(x), R = findRig(x);
                remSeg(L, x, time);
                remSeg(x, R, time);
                addSeg(L, R, time+1);
            }
        }
    }
    sort(segLR.begin(), segLR.end(), cmpSegLR);
    sort(segRL.begin(), segRL.end(), cmpSegRL);
    for (int i = 0; i < segLR.size(); i++) {
        int a = segLR[i].a;
        int b = segLR[i].b;
        tSegLR.update(1, tMax, 1, a, b, i);
    }
    for (int i = 0; i < segRL.size(); i++) {
        int a = segRL[i].a;
        int b = segRL[i].b;
        tSegRL.update(1, tMax, 1, a, b, i);
    }
}

void rayLR(vector<int> seg, vector<int> idQ) {

    int x0 = maxN, pp = -1;
    for (int i = idQ.size()-1; i >= 0; i--) {
        int id = idQ[i];
        while (pp < (int)seg.size()-1 && segLR[seg[pp+1]].R >= que[id].x) {
            pp++;
            x0 = min(x0, segLR[seg[pp]].L);
        }
        if (pp != -1) res[que[id].id] = max(res[que[id].id], que[id].x - x0);
    }
}

void rayRL(vector<int> seg, vector<int> idQ) {

    int y0 = -maxN, pp = -1;
    for (auto id : idQ) {
        while (pp < (int)seg.size()-1 && segRL[seg[pp+1]].L <= que[id].x) {
            pp++;
            y0 = max(y0, segRL[seg[pp]].R);
        }
        if (pp != -1) res[que[id].id] = max(res[que[id].id], y0 - que[id].x);
    }
}

void solve(int l, int r, int id, vector<int> curQ) {

    if (curQ.size() == 0) return;
    rayLR(tSegLR.t[id], curQ);
    rayRL(tSegRL.t[id], curQ);
    if (l == r) return;
    int mid = (r + l)/2;

    vector<int> qLef, qRig;
    for (auto id : curQ) {
        if (que[id].t <= mid) qLef.PB(id);
        else qRig.PB(id);
    }
    solve(l, mid, id*2, qLef);
    solve(mid+1, r, id*2+1, qRig);
}
int cnt[N], impossible[N];
void checkImpossible() {

    vector<pair<pii, int> > check;
    FOR(i, 1, n) {
        check.PB(mp(mp(sto[i].a, 0), sto[i].type));
        check.PB(mp(mp(sto[i].b, 2), sto[i].type));
    }
    FOR(i, 1, Q) {
        check.PB(mp(mp(que[i].t, 1), que[i].id));
    }

    sort(check.begin(), check.end());

    int curCnt = 0;
    for (auto z : check) {
        int time = z.F.F;
        int type = z.F.S;
        int kind = z.S;
        if (type == 1) impossible[kind] = (curCnt < k);
        else {

            if (cnt[kind]) curCnt--;
            if (type == 0) cnt[kind]++;
            else cnt[kind]--;
            if (cnt[kind]) curCnt++;
        }
    }
}

int main() {
    //freopen("NEWHOME.INP", "r", stdin);
    //freopen("NEWHOME.OUT", "w", stdout);
    setup();

    vector<int> allQ;
    FOR(i, 1, Q) allQ.PB(i);

    solve(1, tMax, 1, allQ);


    checkImpossible();
    FOR(i, 1, Q) {
        if (impossible[i]) writeln(-1);
        else writeln(res[i]/2);
    }
}

Compilation message (stderr)

new_home.cpp: In function 'void setup()':
new_home.cpp:142:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < segLR.size(); i++) {
                     ~~^~~~~~~~~~~~~~
new_home.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < segRL.size(); i++) {
                     ~~^~~~~~~~~~~~~~
new_home.cpp: In function 'void checkImpossible()':
new_home.cpp:211:13: warning: unused variable 'time' [-Wunused-variable]
         int time = z.F.F;
             ^~~~

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