oj.uz

답안 #104332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104332 2019-04-05T07:46:49 Z tieunhi 새 집 (APIO18_new_home) C++14
0 / 100
 5000 ms 367320 KB 
#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 300006
using namespace std;

struct Store {
    int x, type, a, b;
};
struct Query {
    int x, t, id;
    bool operator < (const Query &rhs) const {
        return t < rhs.t;
    }
};
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[(3*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;
set<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));
}
void setup() {
    cin >> n >> k >> Q;

    vector<int> allYear;
    FOR(i, 1, n) {
        cin >> sto[i].x >> sto[i].type >> sto[i].a >> sto[i].b;
        sto[i].x *= 2;
        allYear.PB(sto[i].a); allYear.PB(sto[i].b);
    }
    FOR(i, 1, Q) {
        cin >> que[i].x >> 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 = lower_bound(allYear.begin(), allYear.end(), sto[i].b) - allYear.begin() + 1;
    }
    FOR(i, 1, Q) {
        que[i].t = lower_bound(allYear.begin(), allYear.end(), que[i].t) - allYear.begin() + 1;
    }
    tMax = allYear.size();
    sort(que+1, que+Q+1);

    FOR(i, 1, n) {
        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, 1);
        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 {
                curSet.erase(x);
                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) {

    reverse(idQ.begin(), idQ.end());
    int x0 = maxN, pp = -1;
    for (auto id : idQ) {
        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() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    setup();

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

    solve(1, tMax, 1, allQ);


    checkImpossible();
    FOR(i, 1, Q) {
        if (impossible[i]) cout <<-1<<'\n';
        else cout <<res[i]/2<<'\n';
    }
}

Compilation message

new_home.cpp: In function 'void setup()':
new_home.cpp:136:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < segLR.size(); i++) {
                     ~~^~~~~~~~~~~~~~
new_home.cpp:141: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:205:13: warning: unused variable 'time' [-Wunused-variable]
         int time = z.F.F;
             ^~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 176504 KB Output is correct
2 Correct 169 ms 176476 KB Output is correct
3 Correct 180 ms 176560 KB Output is correct
4 Incorrect 184 ms 176504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 176504 KB Output is correct
2 Correct 169 ms 176476 KB Output is correct
3 Correct 180 ms 176560 KB Output is correct
4 Incorrect 184 ms 176504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4776 ms 339632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5051 ms 367320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 176504 KB Output is correct
2 Correct 169 ms 176476 KB Output is correct
3 Correct 180 ms 176560 KB Output is correct
4 Incorrect 184 ms 176504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 176504 KB Output is correct
2 Correct 169 ms 176476 KB Output is correct
3 Correct 180 ms 176560 KB Output is correct
4 Incorrect 184 ms 176504 KB Output isn't correct
5 Halted 0 ms 0 KB -