oj.uz

Submission #104354

# Submission time Handle Problem Language Result Execution time Memory
104354 2019-04-05T15:01:15 Z tieunhi New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 284756 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 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) {

    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() {
    //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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63736 KB Output is correct
2 Correct 65 ms 63708 KB Output is correct
3 Correct 64 ms 63736 KB Output is correct
4 Correct 62 ms 63708 KB Output is correct
5 Correct 69 ms 63864 KB Output is correct
6 Correct 75 ms 64120 KB Output is correct
7 Correct 68 ms 64120 KB Output is correct
8 Correct 72 ms 64044 KB Output is correct
9 Correct 94 ms 64120 KB Output is correct
10 Correct 89 ms 64168 KB Output is correct
11 Correct 75 ms 64092 KB Output is correct
12 Correct 74 ms 64112 KB Output is correct
13 Correct 78 ms 64120 KB Output is correct
14 Correct 78 ms 63992 KB Output is correct
15 Correct 71 ms 64120 KB Output is correct
16 Correct 68 ms 64120 KB Output is correct
17 Correct 74 ms 64248 KB Output is correct
18 Correct 70 ms 64120 KB Output is correct
19 Correct 73 ms 64120 KB Output is correct
20 Correct 74 ms 64096 KB Output is correct
21 Correct 70 ms 63864 KB Output is correct
22 Correct 73 ms 64120 KB Output is correct
23 Correct 79 ms 64120 KB Output is correct
24 Correct 74 ms 64120 KB Output is correct
25 Correct 75 ms 64248 KB Output is correct
26 Correct 71 ms 64104 KB Output is correct
27 Correct 65 ms 63996 KB Output is correct
28 Correct 75 ms 64120 KB Output is correct
29 Correct 75 ms 63992 KB Output is correct
30 Correct 78 ms 63996 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63736 KB Output is correct
2 Correct 65 ms 63708 KB Output is correct
3 Correct 64 ms 63736 KB Output is correct
4 Correct 62 ms 63708 KB Output is correct
5 Correct 69 ms 63864 KB Output is correct
6 Correct 75 ms 64120 KB Output is correct
7 Correct 68 ms 64120 KB Output is correct
8 Correct 72 ms 64044 KB Output is correct
9 Correct 94 ms 64120 KB Output is correct
10 Correct 89 ms 64168 KB Output is correct
11 Correct 75 ms 64092 KB Output is correct
12 Correct 74 ms 64112 KB Output is correct
13 Correct 78 ms 64120 KB Output is correct
14 Correct 78 ms 63992 KB Output is correct
15 Correct 71 ms 64120 KB Output is correct
16 Correct 68 ms 64120 KB Output is correct
17 Correct 74 ms 64248 KB Output is correct
18 Correct 70 ms 64120 KB Output is correct
19 Correct 73 ms 64120 KB Output is correct
20 Correct 74 ms 64096 KB Output is correct
21 Correct 70 ms 63864 KB Output is correct
22 Correct 73 ms 64120 KB Output is correct
23 Correct 79 ms 64120 KB Output is correct
24 Correct 74 ms 64120 KB Output is correct
25 Correct 75 ms 64248 KB Output is correct
26 Correct 71 ms 64104 KB Output is correct
27 Correct 65 ms 63996 KB Output is correct
28 Correct 75 ms 64120 KB Output is correct
29 Correct 75 ms 63992 KB Output is correct
30 Correct 78 ms 63996 KB Output is correct
31 Correct 1797 ms 126824 KB Output is correct
32 Correct 167 ms 74028 KB Output is correct
33 Correct 1827 ms 124964 KB Output is correct
34 Correct 1751 ms 125724 KB Output is correct
35 Correct 1711 ms 126096 KB Output is correct
36 Correct 1935 ms 126220 KB Output is correct
37 Correct 1322 ms 120408 KB Output is correct
38 Correct 1115 ms 119992 KB Output is correct
39 Correct 870 ms 113276 KB Output is correct
40 Correct 814 ms 114776 KB Output is correct
41 Correct 1491 ms 119656 KB Output is correct
42 Correct 1598 ms 120804 KB Output is correct
43 Correct 174 ms 74552 KB Output is correct
44 Correct 1591 ms 119736 KB Output is correct
45 Correct 1508 ms 115820 KB Output is correct
46 Correct 1185 ms 109032 KB Output is correct
47 Correct 637 ms 106904 KB Output is correct
48 Correct 572 ms 104468 KB Output is correct
49 Correct 816 ms 111020 KB Output is correct
50 Correct 1161 ms 118536 KB Output is correct
51 Correct 828 ms 108928 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5051 ms 284756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5059 ms 250156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63736 KB Output is correct
2 Correct 65 ms 63708 KB Output is correct
3 Correct 64 ms 63736 KB Output is correct
4 Correct 62 ms 63708 KB Output is correct
5 Correct 69 ms 63864 KB Output is correct
6 Correct 75 ms 64120 KB Output is correct
7 Correct 68 ms 64120 KB Output is correct
8 Correct 72 ms 64044 KB Output is correct
9 Correct 94 ms 64120 KB Output is correct
10 Correct 89 ms 64168 KB Output is correct
11 Correct 75 ms 64092 KB Output is correct
12 Correct 74 ms 64112 KB Output is correct
13 Correct 78 ms 64120 KB Output is correct
14 Correct 78 ms 63992 KB Output is correct
15 Correct 71 ms 64120 KB Output is correct
16 Correct 68 ms 64120 KB Output is correct
17 Correct 74 ms 64248 KB Output is correct
18 Correct 70 ms 64120 KB Output is correct
19 Correct 73 ms 64120 KB Output is correct
20 Correct 74 ms 64096 KB Output is correct
21 Correct 70 ms 63864 KB Output is correct
22 Correct 73 ms 64120 KB Output is correct
23 Correct 79 ms 64120 KB Output is correct
24 Correct 74 ms 64120 KB Output is correct
25 Correct 75 ms 64248 KB Output is correct
26 Correct 71 ms 64104 KB Output is correct
27 Correct 65 ms 63996 KB Output is correct
28 Correct 75 ms 64120 KB Output is correct
29 Correct 75 ms 63992 KB Output is correct
30 Correct 78 ms 63996 KB Output is correct
31 Correct 1797 ms 126824 KB Output is correct
32 Correct 167 ms 74028 KB Output is correct
33 Correct 1827 ms 124964 KB Output is correct
34 Correct 1751 ms 125724 KB Output is correct
35 Correct 1711 ms 126096 KB Output is correct
36 Correct 1935 ms 126220 KB Output is correct
37 Correct 1322 ms 120408 KB Output is correct
38 Correct 1115 ms 119992 KB Output is correct
39 Correct 870 ms 113276 KB Output is correct
40 Correct 814 ms 114776 KB Output is correct
41 Correct 1491 ms 119656 KB Output is correct
42 Correct 1598 ms 120804 KB Output is correct
43 Correct 174 ms 74552 KB Output is correct
44 Correct 1591 ms 119736 KB Output is correct
45 Correct 1508 ms 115820 KB Output is correct
46 Correct 1185 ms 109032 KB Output is correct
47 Correct 637 ms 106904 KB Output is correct
48 Correct 572 ms 104468 KB Output is correct
49 Correct 816 ms 111020 KB Output is correct
50 Correct 1161 ms 118536 KB Output is correct
51 Correct 828 ms 108928 KB Output is correct
52 Correct 1298 ms 118884 KB Output is correct
53 Correct 1303 ms 118756 KB Output is correct
54 Correct 1634 ms 123844 KB Output is correct
55 Correct 1356 ms 122212 KB Output is correct
56 Correct 1191 ms 122180 KB Output is correct
57 Correct 1515 ms 120436 KB Output is correct
58 Correct 1414 ms 121308 KB Output is correct
59 Correct 1409 ms 122020 KB Output is correct
60 Correct 1621 ms 120996 KB Output is correct
61 Correct 195 ms 80144 KB Output is correct
62 Correct 1143 ms 120524 KB Output is correct
63 Correct 1497 ms 124604 KB Output is correct
64 Correct 1391 ms 126308 KB Output is correct
65 Correct 1581 ms 127332 KB Output is correct
66 Correct 1481 ms 122588 KB Output is correct
67 Correct 306 ms 83040 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63736 KB Output is correct
2 Correct 65 ms 63708 KB Output is correct
3 Correct 64 ms 63736 KB Output is correct
4 Correct 62 ms 63708 KB Output is correct
5 Correct 69 ms 63864 KB Output is correct
6 Correct 75 ms 64120 KB Output is correct
7 Correct 68 ms 64120 KB Output is correct
8 Correct 72 ms 64044 KB Output is correct
9 Correct 94 ms 64120 KB Output is correct
10 Correct 89 ms 64168 KB Output is correct
11 Correct 75 ms 64092 KB Output is correct
12 Correct 74 ms 64112 KB Output is correct
13 Correct 78 ms 64120 KB Output is correct
14 Correct 78 ms 63992 KB Output is correct
15 Correct 71 ms 64120 KB Output is correct
16 Correct 68 ms 64120 KB Output is correct
17 Correct 74 ms 64248 KB Output is correct
18 Correct 70 ms 64120 KB Output is correct
19 Correct 73 ms 64120 KB Output is correct
20 Correct 74 ms 64096 KB Output is correct
21 Correct 70 ms 63864 KB Output is correct
22 Correct 73 ms 64120 KB Output is correct
23 Correct 79 ms 64120 KB Output is correct
24 Correct 74 ms 64120 KB Output is correct
25 Correct 75 ms 64248 KB Output is correct
26 Correct 71 ms 64104 KB Output is correct
27 Correct 65 ms 63996 KB Output is correct
28 Correct 75 ms 64120 KB Output is correct
29 Correct 75 ms 63992 KB Output is correct
30 Correct 78 ms 63996 KB Output is correct
31 Correct 1797 ms 126824 KB Output is correct
32 Correct 167 ms 74028 KB Output is correct
33 Correct 1827 ms 124964 KB Output is correct
34 Correct 1751 ms 125724 KB Output is correct
35 Correct 1711 ms 126096 KB Output is correct
36 Correct 1935 ms 126220 KB Output is correct
37 Correct 1322 ms 120408 KB Output is correct
38 Correct 1115 ms 119992 KB Output is correct
39 Correct 870 ms 113276 KB Output is correct
40 Correct 814 ms 114776 KB Output is correct
41 Correct 1491 ms 119656 KB Output is correct
42 Correct 1598 ms 120804 KB Output is correct
43 Correct 174 ms 74552 KB Output is correct
44 Correct 1591 ms 119736 KB Output is correct
45 Correct 1508 ms 115820 KB Output is correct
46 Correct 1185 ms 109032 KB Output is correct
47 Correct 637 ms 106904 KB Output is correct
48 Correct 572 ms 104468 KB Output is correct
49 Correct 816 ms 111020 KB Output is correct
50 Correct 1161 ms 118536 KB Output is correct
51 Correct 828 ms 108928 KB Output is correct
52 Execution timed out 5051 ms 284756 KB Time limit exceeded
53 Halted 0 ms 0 KB -