답안 #49158 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49158	2018-05-22T20:39:35 Z	ainta	새 집 (APIO18_new_home)	C++17	57 / 100	5000 ms	289024 KB

new_home

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#define N_ 301000
#define SZ 524288
#define pii pair<int,int>
using namespace std;
int n, Q, K, X[N_];
const int INF = 1e9;
struct Store {
    int x, col, b, e;
}w[N_];
vector<int>G[N_];
struct Query {
    int x, t, num;
    bool operator<(const Query &p)const {
        return t < p.t;
    }
}P[N_];
int TT[N_];
struct Seg {
    int b, e, t;
    bool operator<(const Seg &p)const {
        return b != p.b ? b < p.b : e < p.e;
    }
};
struct AA {
    int x, t, ck;
    bool operator <(const AA &p)const {
        return t != p.t ? t<p.t : ck>p.ck;
    }
}U[N_ * 2];
 
struct Order {
    int x, num;
    bool operator<(const Order &p)const {
        return x < p.x;
    }
}ord[N_];
 
int TX[N_];
 
set<Seg>SS;
 
int RN;
struct PP {
    int ck, t, b, e, flag, x, num;
    bool operator<(const PP &p)const {
        return t < p.t;
    }
}R[15010000];
int RC;
 
pii Range(int b, int e) {
    int bb = lower_bound(X + 1, X + Q + 1, b) - X;
    int ee = lower_bound(X + 1, X + Q + 1, e + 1) - X - 1;
    return { bb,ee };
}
 
struct RR {
    int b, e;
    bool operator<(const RR &p)const {
        return b < p.b;
    }
};
vector<RR>VV;
 
void Add(int ck, int t1, int t2, int b, int e, int x) {
    if (x > 8e8 || x < -8e8)return;
    RN++;
    R[RC++] = { ck,t1,b,e,1,x, RN};
    R[RC++] = { ck,t2 + 1,b,e,-1,x, RN};
    VV.push_back({ t1,t2 });
}
 
void Make2(int t1, int t2, int x1, int x2) {
    x1 = ord[x1].x, x2 = ord[x2].x;
    if (x1 > x2 || t1 > t2)return;
    int mid = (x1 + x2) / 2;
    pii tp = Range(x1, mid);
    if (tp.first <= tp.second) {
        Add(0, t1, t2, tp.first, tp.second, x1);
    }
    tp = Range(mid + 1, x2);
    if (tp.first <= tp.second) {
        Add(1, t1, t2, tp.first, tp.second, x2);
    }
}
void Put(int x, int t) {
    auto it = SS.lower_bound({ x,0,0 });
    it--;
    int bb = it->b, ee = it->e;
    Make2((it->t), t - 1, bb, ee);
    SS.erase(it);
    SS.insert({ bb,x,t });
    SS.insert({ x, ee, t });
}
void Del(int x, int t) {
    auto it = SS.lower_bound({ x, -INF, 0 });
    int ee = it->e;
    Make2(it->t, t - 1, x, ee);
    auto it2 = it;
    it--;
    int bb = it->b;
    Make2(it->t, t - 1, bb, x);
    SS.erase(it);
    SS.erase(it2);
    SS.insert({ bb,ee,t });
}
int SSum[N_];
void Make(int col) {
    VV.clear();
    SS.clear();
    int cnt = 0;
    for (auto &t : G[col]) {
        ord[cnt++] = { w[t].x, t };
    }
    ord[cnt++] = { -INF, -1 };
    ord[cnt++] = { INF, -2 };
    sort(ord, ord + cnt);
    int i;
    for (i = 0; i < cnt; i++) {
        if (ord[i].num >= 0) {
            TX[ord[i].num] = i;
        }
    }
    SS.insert({ 0,cnt - 1,1 });
    int cc = 0;
    for (auto &t : G[col]) {
        U[cc++] = { TX[t], w[t].b, 1 };
        U[cc++] = { TX[t], w[t].e + 1, -1 };
    }
    sort(U, U + cc);
    for (i = 0; i < cc; i++) {
        if (U[i].ck == 1) {
            Put(U[i].x, U[i].t);
        }
        else {
            Del(U[i].x, U[i].t);
        }
    }
    auto it = SS.begin();
    Make2(it->t, Q, it->b, it->e);
    if (VV.empty())return;
    sort(VV.begin(), VV.end());
    int ee = -1, bb = -1;
    for (auto &x : VV) {
        if (ee < x.b) {
            if (ee != -1) {
                SSum[bb]++;
                SSum[ee + 1]--;
            }
            bb = x.b;
        }
        ee = max(ee, x.e);
    }
    SSum[bb]++, SSum[ee + 1]--;
}
int vv[7510000];
priority_queue<pii>PQ[SZ + SZ][2];
void Put2(int nd, int ck, int x, int num) {
    if (ck == 0) {
        PQ[nd][ck].push({ -x,num });
    }
    else {
        PQ[nd][ck].push({ x, num });
    }
}
void Put(int b, int e, int x, int ck, int num) {
    b += SZ, e += SZ;
    while(b<=e){
        if (b & 1) {
            Put2(b, ck, x, num);
        }
        if (!(e & 1)) {
            Put2(e, ck, x, num);
        }
        b = (b + 1) >> 1, e = (e - 1) >> 1;
    }
}
int Res[N_];
int Get(int x, int ox) {
    int nd = x + SZ, r = 0;
    while (nd) {
        while (!PQ[nd][0].empty()) {
            pii tp = PQ[nd][0].top();
            if (!vv[tp.second]) {
                r = max(r, ox + tp.first);
                break;
            }
            PQ[nd][0].pop();
        }
        while (!PQ[nd][1].empty()) {
            pii tp = PQ[nd][1].top();
            if (!vv[tp.second]) {
                r = max(r, tp.first - ox);
                break;
            }
            PQ[nd][1].pop();
        }
        nd >>= 1;
    }
    return r;
}
int main() {
    int i;
    scanf("%d%d%d", &n, &K, &Q);
    for (i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &w[i].x, &w[i].col, &w[i].b, &w[i].e);
        G[w[i].col].push_back(i);
    }
    for (i = 1; i <= Q; i++) {
        scanf("%d%d", &P[i].x, &P[i].t);
        TT[i] = P[i].t;
        X[i] = P[i].x;
        P[i].num = i;
    }
    sort(X + 1, X + Q + 1);
    sort(TT + 1, TT + Q + 1);
    for (i = 1; i <= n; i++) {
        w[i].b = lower_bound(TT + 1, TT + Q + 1, w[i].b) - TT;
        w[i].e = lower_bound(TT + 1, TT + Q + 1, w[i].e + 1) - TT - 1;
    }
    for (i = 1; i <= Q; i++) {
        P[i].t = lower_bound(TT + 1, TT + Q + 1, P[i].t) - TT;
    }
    for (i = 1; i <= K; i++) {
        Make(i);
    }
    sort(R, R + RC);
    sort(P + 1, P + Q + 1);
    int pv = 0;
    for (i = 1; i <= Q; i++)SSum[i] += SSum[i - 1];
    for (i = 1; i <= Q; i++) {
        while (pv < RC && R[pv].t <= P[i].t) {
            if (R[pv].flag == 1) {
                Put(R[pv].b, R[pv].e, R[pv].x, R[pv].ck, R[pv].num);
            }
            else {
                vv[R[pv].num] = 1;
            }
            pv++;
        }
        int x = lower_bound(X + 1, X + Q + 1, P[i].x) - X;
        Res[P[i].num] = Get(x, P[i].x);
        if (SSum[P[i].t] != K)Res[P[i].num] = 1e9;
    }
    for (i = 1; i <= Q; i++) {
        if (Res[i] > 3e8)printf("-1\n");
        else printf("%d\n", Res[i]);
    }
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:209:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:211:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &w[i].x, &w[i].col, &w[i].b, &w[i].e);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:215:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &P[i].x, &P[i].t);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	73120 KB	Output is correct
2	Correct	69 ms	73148 KB	Output is correct
3	Correct	67 ms	73236 KB	Output is correct
4	Correct	69 ms	73280 KB	Output is correct
5	Correct	71 ms	73468 KB	Output is correct
6	Correct	71 ms	73524 KB	Output is correct
7	Correct	70 ms	73536 KB	Output is correct
8	Correct	69 ms	73556 KB	Output is correct
9	Correct	62 ms	73556 KB	Output is correct
10	Correct	71 ms	73564 KB	Output is correct
11	Correct	58 ms	73580 KB	Output is correct
12	Correct	69 ms	73580 KB	Output is correct
13	Correct	65 ms	73580 KB	Output is correct
14	Correct	59 ms	73580 KB	Output is correct
15	Correct	68 ms	73580 KB	Output is correct
16	Correct	62 ms	73580 KB	Output is correct
17	Correct	67 ms	73580 KB	Output is correct
18	Correct	61 ms	73584 KB	Output is correct
19	Correct	61 ms	73672 KB	Output is correct
20	Correct	69 ms	73672 KB	Output is correct
21	Correct	62 ms	73672 KB	Output is correct
22	Correct	60 ms	73672 KB	Output is correct
23	Correct	70 ms	73672 KB	Output is correct
24	Correct	62 ms	73672 KB	Output is correct
25	Correct	70 ms	73672 KB	Output is correct
26	Correct	73 ms	73672 KB	Output is correct
27	Correct	73 ms	73672 KB	Output is correct
28	Correct	68 ms	73672 KB	Output is correct
29	Correct	67 ms	73672 KB	Output is correct
30	Correct	79 ms	73672 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	73120 KB	Output is correct
2	Correct	69 ms	73148 KB	Output is correct
3	Correct	67 ms	73236 KB	Output is correct
4	Correct	69 ms	73280 KB	Output is correct
5	Correct	71 ms	73468 KB	Output is correct
6	Correct	71 ms	73524 KB	Output is correct
7	Correct	70 ms	73536 KB	Output is correct
8	Correct	69 ms	73556 KB	Output is correct
9	Correct	62 ms	73556 KB	Output is correct
10	Correct	71 ms	73564 KB	Output is correct
11	Correct	58 ms	73580 KB	Output is correct
12	Correct	69 ms	73580 KB	Output is correct
13	Correct	65 ms	73580 KB	Output is correct
14	Correct	59 ms	73580 KB	Output is correct
15	Correct	68 ms	73580 KB	Output is correct
16	Correct	62 ms	73580 KB	Output is correct
17	Correct	67 ms	73580 KB	Output is correct
18	Correct	61 ms	73584 KB	Output is correct
19	Correct	61 ms	73672 KB	Output is correct
20	Correct	69 ms	73672 KB	Output is correct
21	Correct	62 ms	73672 KB	Output is correct
22	Correct	60 ms	73672 KB	Output is correct
23	Correct	70 ms	73672 KB	Output is correct
24	Correct	62 ms	73672 KB	Output is correct
25	Correct	70 ms	73672 KB	Output is correct
26	Correct	73 ms	73672 KB	Output is correct
27	Correct	73 ms	73672 KB	Output is correct
28	Correct	68 ms	73672 KB	Output is correct
29	Correct	67 ms	73672 KB	Output is correct
30	Correct	79 ms	73672 KB	Output is correct
31	Correct	1363 ms	129912 KB	Output is correct
32	Correct	388 ms	129912 KB	Output is correct
33	Correct	880 ms	129912 KB	Output is correct
34	Correct	1131 ms	131372 KB	Output is correct
35	Correct	1082 ms	131372 KB	Output is correct
36	Correct	828 ms	131372 KB	Output is correct
37	Correct	868 ms	131372 KB	Output is correct
38	Correct	605 ms	131372 KB	Output is correct
39	Correct	547 ms	131372 KB	Output is correct
40	Correct	552 ms	131372 KB	Output is correct
41	Correct	1083 ms	131372 KB	Output is correct
42	Correct	1077 ms	131372 KB	Output is correct
43	Correct	173 ms	131372 KB	Output is correct
44	Correct	1154 ms	131372 KB	Output is correct
45	Correct	1006 ms	131372 KB	Output is correct
46	Correct	917 ms	131372 KB	Output is correct
47	Correct	444 ms	131372 KB	Output is correct
48	Correct	444 ms	131372 KB	Output is correct
49	Correct	585 ms	131372 KB	Output is correct
50	Correct	658 ms	131372 KB	Output is correct
51	Correct	560 ms	131372 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3854 ms	225116 KB	Output is correct
2	Correct	2374 ms	225116 KB	Output is correct
3	Correct	3404 ms	247964 KB	Output is correct
4	Correct	3298 ms	247964 KB	Output is correct
5	Correct	2164 ms	247964 KB	Output is correct
6	Correct	2211 ms	247964 KB	Output is correct
7	Correct	2573 ms	248708 KB	Output is correct
8	Correct	3057 ms	248708 KB	Output is correct
9	Correct	3429 ms	248708 KB	Output is correct
10	Correct	2527 ms	248708 KB	Output is correct
11	Correct	1532 ms	248708 KB	Output is correct
12	Correct	2082 ms	248708 KB	Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	73120 KB	Output is correct
2	Correct	69 ms	73148 KB	Output is correct
3	Correct	67 ms	73236 KB	Output is correct
4	Correct	69 ms	73280 KB	Output is correct
5	Correct	71 ms	73468 KB	Output is correct
6	Correct	71 ms	73524 KB	Output is correct
7	Correct	70 ms	73536 KB	Output is correct
8	Correct	69 ms	73556 KB	Output is correct
9	Correct	62 ms	73556 KB	Output is correct
10	Correct	71 ms	73564 KB	Output is correct
11	Correct	58 ms	73580 KB	Output is correct
12	Correct	69 ms	73580 KB	Output is correct
13	Correct	65 ms	73580 KB	Output is correct
14	Correct	59 ms	73580 KB	Output is correct
15	Correct	68 ms	73580 KB	Output is correct
16	Correct	62 ms	73580 KB	Output is correct
17	Correct	67 ms	73580 KB	Output is correct
18	Correct	61 ms	73584 KB	Output is correct
19	Correct	61 ms	73672 KB	Output is correct
20	Correct	69 ms	73672 KB	Output is correct
21	Correct	62 ms	73672 KB	Output is correct
22	Correct	60 ms	73672 KB	Output is correct
23	Correct	70 ms	73672 KB	Output is correct
24	Correct	62 ms	73672 KB	Output is correct
25	Correct	70 ms	73672 KB	Output is correct
26	Correct	73 ms	73672 KB	Output is correct
27	Correct	73 ms	73672 KB	Output is correct
28	Correct	68 ms	73672 KB	Output is correct
29	Correct	67 ms	73672 KB	Output is correct
30	Correct	79 ms	73672 KB	Output is correct
31	Correct	1363 ms	129912 KB	Output is correct
32	Correct	388 ms	129912 KB	Output is correct
33	Correct	880 ms	129912 KB	Output is correct
34	Correct	1131 ms	131372 KB	Output is correct
35	Correct	1082 ms	131372 KB	Output is correct
36	Correct	828 ms	131372 KB	Output is correct
37	Correct	868 ms	131372 KB	Output is correct
38	Correct	605 ms	131372 KB	Output is correct
39	Correct	547 ms	131372 KB	Output is correct
40	Correct	552 ms	131372 KB	Output is correct
41	Correct	1083 ms	131372 KB	Output is correct
42	Correct	1077 ms	131372 KB	Output is correct
43	Correct	173 ms	131372 KB	Output is correct
44	Correct	1154 ms	131372 KB	Output is correct
45	Correct	1006 ms	131372 KB	Output is correct
46	Correct	917 ms	131372 KB	Output is correct
47	Correct	444 ms	131372 KB	Output is correct
48	Correct	444 ms	131372 KB	Output is correct
49	Correct	585 ms	131372 KB	Output is correct
50	Correct	658 ms	131372 KB	Output is correct
51	Correct	560 ms	131372 KB	Output is correct
52	Correct	687 ms	289024 KB	Output is correct
53	Correct	614 ms	289024 KB	Output is correct
54	Correct	1113 ms	289024 KB	Output is correct
55	Correct	885 ms	289024 KB	Output is correct
56	Correct	775 ms	289024 KB	Output is correct
57	Correct	1060 ms	289024 KB	Output is correct
58	Correct	934 ms	289024 KB	Output is correct
59	Correct	798 ms	289024 KB	Output is correct
60	Correct	1025 ms	289024 KB	Output is correct
61	Correct	229 ms	289024 KB	Output is correct
62	Correct	582 ms	289024 KB	Output is correct
63	Correct	746 ms	289024 KB	Output is correct
64	Correct	820 ms	289024 KB	Output is correct
65	Correct	947 ms	289024 KB	Output is correct
66	Correct	1069 ms	289024 KB	Output is correct
67	Correct	559 ms	289024 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	73120 KB	Output is correct
2	Correct	69 ms	73148 KB	Output is correct
3	Correct	67 ms	73236 KB	Output is correct
4	Correct	69 ms	73280 KB	Output is correct
5	Correct	71 ms	73468 KB	Output is correct
6	Correct	71 ms	73524 KB	Output is correct
7	Correct	70 ms	73536 KB	Output is correct
8	Correct	69 ms	73556 KB	Output is correct
9	Correct	62 ms	73556 KB	Output is correct
10	Correct	71 ms	73564 KB	Output is correct
11	Correct	58 ms	73580 KB	Output is correct
12	Correct	69 ms	73580 KB	Output is correct
13	Correct	65 ms	73580 KB	Output is correct
14	Correct	59 ms	73580 KB	Output is correct
15	Correct	68 ms	73580 KB	Output is correct
16	Correct	62 ms	73580 KB	Output is correct
17	Correct	67 ms	73580 KB	Output is correct
18	Correct	61 ms	73584 KB	Output is correct
19	Correct	61 ms	73672 KB	Output is correct
20	Correct	69 ms	73672 KB	Output is correct
21	Correct	62 ms	73672 KB	Output is correct
22	Correct	60 ms	73672 KB	Output is correct
23	Correct	70 ms	73672 KB	Output is correct
24	Correct	62 ms	73672 KB	Output is correct
25	Correct	70 ms	73672 KB	Output is correct
26	Correct	73 ms	73672 KB	Output is correct
27	Correct	73 ms	73672 KB	Output is correct
28	Correct	68 ms	73672 KB	Output is correct
29	Correct	67 ms	73672 KB	Output is correct
30	Correct	79 ms	73672 KB	Output is correct
31	Correct	1363 ms	129912 KB	Output is correct
32	Correct	388 ms	129912 KB	Output is correct
33	Correct	880 ms	129912 KB	Output is correct
34	Correct	1131 ms	131372 KB	Output is correct
35	Correct	1082 ms	131372 KB	Output is correct
36	Correct	828 ms	131372 KB	Output is correct
37	Correct	868 ms	131372 KB	Output is correct
38	Correct	605 ms	131372 KB	Output is correct
39	Correct	547 ms	131372 KB	Output is correct
40	Correct	552 ms	131372 KB	Output is correct
41	Correct	1083 ms	131372 KB	Output is correct
42	Correct	1077 ms	131372 KB	Output is correct
43	Correct	173 ms	131372 KB	Output is correct
44	Correct	1154 ms	131372 KB	Output is correct
45	Correct	1006 ms	131372 KB	Output is correct
46	Correct	917 ms	131372 KB	Output is correct
47	Correct	444 ms	131372 KB	Output is correct
48	Correct	444 ms	131372 KB	Output is correct
49	Correct	585 ms	131372 KB	Output is correct
50	Correct	658 ms	131372 KB	Output is correct
51	Correct	560 ms	131372 KB	Output is correct
52	Correct	3854 ms	225116 KB	Output is correct
53	Correct	2374 ms	225116 KB	Output is correct
54	Correct	3404 ms	247964 KB	Output is correct
55	Correct	3298 ms	247964 KB	Output is correct
56	Correct	2164 ms	247964 KB	Output is correct
57	Correct	2211 ms	247964 KB	Output is correct
58	Correct	2573 ms	248708 KB	Output is correct
59	Correct	3057 ms	248708 KB	Output is correct
60	Correct	3429 ms	248708 KB	Output is correct
61	Correct	2527 ms	248708 KB	Output is correct
62	Correct	1532 ms	248708 KB	Output is correct
63	Correct	2082 ms	248708 KB	Output is correct
64	Execution timed out	5025 ms	289024 KB	Time limit exceeded
65	Halted	0 ms	0 KB	-

답안 #49158

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0