답안 #60147 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60147	2018-07-23T18:14:49 Z	duality	새 집 (APIO18_new_home)	C++11	45 / 100	5000 ms	372416 KB

new_home

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

struct op { int time,t,x,i; };
bool comp(op a,op b) {
    if (a.time == b.time) return a.t > b.t;
    else return a.time < b.time;
}
vector<op> oper;
multiset<int> stores[300000];
int ans[300000];
map<int,int> M;
int query(int x) {
    auto it = M.lower_bound(x);
    int m = 0;
    if (it != M.end()) m = max(m,it->second-(it->first-x));
    if (it != M.begin()) it--,m = max(m,it->second-(x-it->first));
    return m;
}
int update(int x,int h) {
    //cout<<"UPDATE "<<x<<","<<h<<endl;
    if (query(x) >= h) return 0;
    //cout<<"XXX"<<endl;
    auto it = M.lower_bound(x);
    while (it != M.end()) {
        if (it->second > h-(it->first-x)) break;
        else it = M.erase(it);
    }
    M[x] = h;
    it = M.find(x);
    while (1) {
        if (it == M.begin()) break;
        it--;
        if (it->second > h-(x-it->first)) break;
        else it = M.erase(it);
    }
    return 0;
}
int main() {
    int i;
    int n,k,q;
    int x,t,a,b,l,y;
    int sub34 = 1;
    scanf("%d %d %d",&n,&k,&q);
    for (i = 0; i < n; i++) {
        scanf("%d %d %d %d",&x,&t,&a,&b);
        oper.pb((op){a,t,x,-1});
        oper.pb((op){b,-t,x,-1});
        sub34 &= (a == 1);
    }
    for (i = 0; i < q; i++) {
        scanf("%d %d",&l,&y);
        oper.pb((op){y,0,l,i});
    }
    sort(oper.begin(),oper.end(),comp);

    int j;
    if (sub34) {
        int f = 0;
        for (i = 0; i < oper.size(); i++) {
            if (oper[i].t > 0) stores[oper[i].t-1].insert(oper[i].x);
            else {
                if (!f) {
                    //cout<<"here"<<endl;
                    for (j = 0; j < k; j++) {
                        stores[j].insert(-3e8);
                        stores[j].insert(3e8);
                        for (auto it = ++stores[j].begin(); it != stores[j].end(); it++) {
                            auto it2 = it;
                            it2--;
                            update(*it+*it2,*it-*it2);
                        }
                    }
                    f = 1;
                    //for (auto it = M.begin();it!=M.end();it++){
                    //    cout<<it->first<<","<<it->second<<endl;
                    //}
                }
                if (oper[i].t < 0) {
                    int p = -oper[i].t-1;
                    auto it = stores[p].find(oper[i].x);
                    auto it2 = it;
                    it++,it2--;
                    update(*it+*it2,*it-*it2);
                    stores[p].erase(stores[p].find(oper[i].x));
                }
                else {
                    ans[oper[i].i] = query(2*oper[i].x)/2;
                    if (ans[oper[i].i] > 1e8) ans[oper[i].i] = -1;
                }
            }
        }
    }
    else {
        for (i = 0; i < oper.size(); i++) {
            if (oper[i].t > 0) stores[oper[i].t-1].insert(oper[i].x);
            else if (oper[i].t < 0) stores[-oper[i].t-1].erase(stores[-oper[i].t-1].find(oper[i].x));
            else {
                int m = 0;
                for (j = 0; j < k; j++) {
                    if (stores[j].empty()) break;
                    else {
                        auto it = stores[j].lower_bound(oper[i].x);
                        int mm = 1e9;
                        if (it != stores[j].end()) mm = min(mm,*it-oper[i].x);
                        if (it != stores[j].begin()) mm = min(mm,oper[i].x-*(--it));
                        m = max(m,mm);
                    }
                }
                if (j < k) ans[oper[i].i] = -1;
                else ans[oper[i].i] = m;
            }
        }
    }
    for (i = 0; i < q; i++) printf("%d\n",ans[i]);

    return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < oper.size(); i++) {
                     ~~^~~~~~~~~~~~~
new_home.cpp:101:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < oper.size(); i++) {
                     ~~^~~~~~~~~~~~~
new_home.cpp:50: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:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&x,&t,&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&l,&y);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14328 KB	Output is correct
2	Correct	18 ms	14568 KB	Output is correct
3	Correct	19 ms	14568 KB	Output is correct
4	Correct	19 ms	14712 KB	Output is correct
5	Correct	17 ms	14712 KB	Output is correct
6	Correct	20 ms	14712 KB	Output is correct
7	Correct	17 ms	14736 KB	Output is correct
8	Correct	20 ms	14760 KB	Output is correct
9	Correct	18 ms	14856 KB	Output is correct
10	Correct	20 ms	14856 KB	Output is correct
11	Correct	20 ms	14864 KB	Output is correct
12	Correct	21 ms	14864 KB	Output is correct
13	Correct	19 ms	14864 KB	Output is correct
14	Correct	18 ms	14880 KB	Output is correct
15	Correct	17 ms	15028 KB	Output is correct
16	Correct	18 ms	15028 KB	Output is correct
17	Correct	17 ms	15028 KB	Output is correct
18	Correct	17 ms	15028 KB	Output is correct
19	Correct	16 ms	15028 KB	Output is correct
20	Correct	16 ms	15028 KB	Output is correct
21	Correct	19 ms	15028 KB	Output is correct
22	Correct	20 ms	15036 KB	Output is correct
23	Correct	18 ms	15056 KB	Output is correct
24	Correct	20 ms	15112 KB	Output is correct
25	Correct	16 ms	15112 KB	Output is correct
26	Correct	19 ms	15116 KB	Output is correct
27	Correct	22 ms	15144 KB	Output is correct
28	Correct	15 ms	15144 KB	Output is correct
29	Correct	16 ms	15164 KB	Output is correct
30	Correct	18 ms	15228 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14328 KB	Output is correct
2	Correct	18 ms	14568 KB	Output is correct
3	Correct	19 ms	14568 KB	Output is correct
4	Correct	19 ms	14712 KB	Output is correct
5	Correct	17 ms	14712 KB	Output is correct
6	Correct	20 ms	14712 KB	Output is correct
7	Correct	17 ms	14736 KB	Output is correct
8	Correct	20 ms	14760 KB	Output is correct
9	Correct	18 ms	14856 KB	Output is correct
10	Correct	20 ms	14856 KB	Output is correct
11	Correct	20 ms	14864 KB	Output is correct
12	Correct	21 ms	14864 KB	Output is correct
13	Correct	19 ms	14864 KB	Output is correct
14	Correct	18 ms	14880 KB	Output is correct
15	Correct	17 ms	15028 KB	Output is correct
16	Correct	18 ms	15028 KB	Output is correct
17	Correct	17 ms	15028 KB	Output is correct
18	Correct	17 ms	15028 KB	Output is correct
19	Correct	16 ms	15028 KB	Output is correct
20	Correct	16 ms	15028 KB	Output is correct
21	Correct	19 ms	15028 KB	Output is correct
22	Correct	20 ms	15036 KB	Output is correct
23	Correct	18 ms	15056 KB	Output is correct
24	Correct	20 ms	15112 KB	Output is correct
25	Correct	16 ms	15112 KB	Output is correct
26	Correct	19 ms	15116 KB	Output is correct
27	Correct	22 ms	15144 KB	Output is correct
28	Correct	15 ms	15144 KB	Output is correct
29	Correct	16 ms	15164 KB	Output is correct
30	Correct	18 ms	15228 KB	Output is correct
31	Correct	3476 ms	22348 KB	Output is correct
32	Correct	130 ms	22348 KB	Output is correct
33	Correct	299 ms	22348 KB	Output is correct
34	Correct	2783 ms	22348 KB	Output is correct
35	Correct	2128 ms	22544 KB	Output is correct
36	Correct	459 ms	22544 KB	Output is correct
37	Correct	232 ms	22544 KB	Output is correct
38	Correct	154 ms	22544 KB	Output is correct
39	Correct	131 ms	22544 KB	Output is correct
40	Correct	150 ms	22544 KB	Output is correct
41	Correct	428 ms	22544 KB	Output is correct
42	Correct	319 ms	22544 KB	Output is correct
43	Correct	116 ms	22544 KB	Output is correct
44	Correct	305 ms	22544 KB	Output is correct
45	Correct	241 ms	22544 KB	Output is correct
46	Correct	134 ms	22544 KB	Output is correct
47	Correct	118 ms	22544 KB	Output is correct
48	Correct	118 ms	22544 KB	Output is correct
49	Correct	135 ms	22544 KB	Output is correct
50	Correct	291 ms	22544 KB	Output is correct
51	Correct	128 ms	22544 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	634 ms	54004 KB	Output is correct
2	Correct	1040 ms	61284 KB	Output is correct
3	Correct	722 ms	103184 KB	Output is correct
4	Correct	675 ms	103184 KB	Output is correct
5	Correct	2595 ms	113560 KB	Output is correct
6	Correct	1290 ms	115392 KB	Output is correct
7	Correct	726 ms	155804 KB	Output is correct
8	Correct	592 ms	155804 KB	Output is correct
9	Correct	594 ms	157728 KB	Output is correct
10	Correct	718 ms	167432 KB	Output is correct
11	Correct	816 ms	179432 KB	Output is correct
12	Correct	656 ms	191840 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	848 ms	192516 KB	Output is correct
2	Correct	471 ms	194312 KB	Output is correct
3	Correct	1793 ms	208508 KB	Output is correct
4	Correct	947 ms	245572 KB	Output is correct
5	Correct	784 ms	245572 KB	Output is correct
6	Correct	891 ms	253156 KB	Output is correct
7	Correct	2842 ms	270064 KB	Output is correct
8	Correct	1917 ms	271208 KB	Output is correct
9	Correct	792 ms	308112 KB	Output is correct
10	Correct	881 ms	308112 KB	Output is correct
11	Correct	870 ms	308200 KB	Output is correct
12	Correct	1243 ms	317852 KB	Output is correct
13	Correct	742 ms	328748 KB	Output is correct
14	Correct	821 ms	340600 KB	Output is correct
15	Correct	822 ms	350008 KB	Output is correct
16	Correct	799 ms	361340 KB	Output is correct
17	Correct	978 ms	372416 KB	Output is correct

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14328 KB	Output is correct
2	Correct	18 ms	14568 KB	Output is correct
3	Correct	19 ms	14568 KB	Output is correct
4	Correct	19 ms	14712 KB	Output is correct
5	Correct	17 ms	14712 KB	Output is correct
6	Correct	20 ms	14712 KB	Output is correct
7	Correct	17 ms	14736 KB	Output is correct
8	Correct	20 ms	14760 KB	Output is correct
9	Correct	18 ms	14856 KB	Output is correct
10	Correct	20 ms	14856 KB	Output is correct
11	Correct	20 ms	14864 KB	Output is correct
12	Correct	21 ms	14864 KB	Output is correct
13	Correct	19 ms	14864 KB	Output is correct
14	Correct	18 ms	14880 KB	Output is correct
15	Correct	17 ms	15028 KB	Output is correct
16	Correct	18 ms	15028 KB	Output is correct
17	Correct	17 ms	15028 KB	Output is correct
18	Correct	17 ms	15028 KB	Output is correct
19	Correct	16 ms	15028 KB	Output is correct
20	Correct	16 ms	15028 KB	Output is correct
21	Correct	19 ms	15028 KB	Output is correct
22	Correct	20 ms	15036 KB	Output is correct
23	Correct	18 ms	15056 KB	Output is correct
24	Correct	20 ms	15112 KB	Output is correct
25	Correct	16 ms	15112 KB	Output is correct
26	Correct	19 ms	15116 KB	Output is correct
27	Correct	22 ms	15144 KB	Output is correct
28	Correct	15 ms	15144 KB	Output is correct
29	Correct	16 ms	15164 KB	Output is correct
30	Correct	18 ms	15228 KB	Output is correct
31	Correct	3476 ms	22348 KB	Output is correct
32	Correct	130 ms	22348 KB	Output is correct
33	Correct	299 ms	22348 KB	Output is correct
34	Correct	2783 ms	22348 KB	Output is correct
35	Correct	2128 ms	22544 KB	Output is correct
36	Correct	459 ms	22544 KB	Output is correct
37	Correct	232 ms	22544 KB	Output is correct
38	Correct	154 ms	22544 KB	Output is correct
39	Correct	131 ms	22544 KB	Output is correct
40	Correct	150 ms	22544 KB	Output is correct
41	Correct	428 ms	22544 KB	Output is correct
42	Correct	319 ms	22544 KB	Output is correct
43	Correct	116 ms	22544 KB	Output is correct
44	Correct	305 ms	22544 KB	Output is correct
45	Correct	241 ms	22544 KB	Output is correct
46	Correct	134 ms	22544 KB	Output is correct
47	Correct	118 ms	22544 KB	Output is correct
48	Correct	118 ms	22544 KB	Output is correct
49	Correct	135 ms	22544 KB	Output is correct
50	Correct	291 ms	22544 KB	Output is correct
51	Correct	128 ms	22544 KB	Output is correct
52	Correct	163 ms	372416 KB	Output is correct
53	Correct	146 ms	372416 KB	Output is correct
54	Correct	231 ms	372416 KB	Output is correct
55	Execution timed out	5031 ms	372416 KB	Time limit exceeded
56	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	14328 KB	Output is correct
2	Correct	18 ms	14568 KB	Output is correct
3	Correct	19 ms	14568 KB	Output is correct
4	Correct	19 ms	14712 KB	Output is correct
5	Correct	17 ms	14712 KB	Output is correct
6	Correct	20 ms	14712 KB	Output is correct
7	Correct	17 ms	14736 KB	Output is correct
8	Correct	20 ms	14760 KB	Output is correct
9	Correct	18 ms	14856 KB	Output is correct
10	Correct	20 ms	14856 KB	Output is correct
11	Correct	20 ms	14864 KB	Output is correct
12	Correct	21 ms	14864 KB	Output is correct
13	Correct	19 ms	14864 KB	Output is correct
14	Correct	18 ms	14880 KB	Output is correct
15	Correct	17 ms	15028 KB	Output is correct
16	Correct	18 ms	15028 KB	Output is correct
17	Correct	17 ms	15028 KB	Output is correct
18	Correct	17 ms	15028 KB	Output is correct
19	Correct	16 ms	15028 KB	Output is correct
20	Correct	16 ms	15028 KB	Output is correct
21	Correct	19 ms	15028 KB	Output is correct
22	Correct	20 ms	15036 KB	Output is correct
23	Correct	18 ms	15056 KB	Output is correct
24	Correct	20 ms	15112 KB	Output is correct
25	Correct	16 ms	15112 KB	Output is correct
26	Correct	19 ms	15116 KB	Output is correct
27	Correct	22 ms	15144 KB	Output is correct
28	Correct	15 ms	15144 KB	Output is correct
29	Correct	16 ms	15164 KB	Output is correct
30	Correct	18 ms	15228 KB	Output is correct
31	Correct	3476 ms	22348 KB	Output is correct
32	Correct	130 ms	22348 KB	Output is correct
33	Correct	299 ms	22348 KB	Output is correct
34	Correct	2783 ms	22348 KB	Output is correct
35	Correct	2128 ms	22544 KB	Output is correct
36	Correct	459 ms	22544 KB	Output is correct
37	Correct	232 ms	22544 KB	Output is correct
38	Correct	154 ms	22544 KB	Output is correct
39	Correct	131 ms	22544 KB	Output is correct
40	Correct	150 ms	22544 KB	Output is correct
41	Correct	428 ms	22544 KB	Output is correct
42	Correct	319 ms	22544 KB	Output is correct
43	Correct	116 ms	22544 KB	Output is correct
44	Correct	305 ms	22544 KB	Output is correct
45	Correct	241 ms	22544 KB	Output is correct
46	Correct	134 ms	22544 KB	Output is correct
47	Correct	118 ms	22544 KB	Output is correct
48	Correct	118 ms	22544 KB	Output is correct
49	Correct	135 ms	22544 KB	Output is correct
50	Correct	291 ms	22544 KB	Output is correct
51	Correct	128 ms	22544 KB	Output is correct
52	Correct	634 ms	54004 KB	Output is correct
53	Correct	1040 ms	61284 KB	Output is correct
54	Correct	722 ms	103184 KB	Output is correct
55	Correct	675 ms	103184 KB	Output is correct
56	Correct	2595 ms	113560 KB	Output is correct
57	Correct	1290 ms	115392 KB	Output is correct
58	Correct	726 ms	155804 KB	Output is correct
59	Correct	592 ms	155804 KB	Output is correct
60	Correct	594 ms	157728 KB	Output is correct
61	Correct	718 ms	167432 KB	Output is correct
62	Correct	816 ms	179432 KB	Output is correct
63	Correct	656 ms	191840 KB	Output is correct
64	Correct	848 ms	192516 KB	Output is correct
65	Correct	471 ms	194312 KB	Output is correct
66	Correct	1793 ms	208508 KB	Output is correct
67	Correct	947 ms	245572 KB	Output is correct
68	Correct	784 ms	245572 KB	Output is correct
69	Correct	891 ms	253156 KB	Output is correct
70	Correct	2842 ms	270064 KB	Output is correct
71	Correct	1917 ms	271208 KB	Output is correct
72	Correct	792 ms	308112 KB	Output is correct
73	Correct	881 ms	308112 KB	Output is correct
74	Correct	870 ms	308200 KB	Output is correct
75	Correct	1243 ms	317852 KB	Output is correct
76	Correct	742 ms	328748 KB	Output is correct
77	Correct	821 ms	340600 KB	Output is correct
78	Correct	822 ms	350008 KB	Output is correct
79	Correct	799 ms	361340 KB	Output is correct
80	Correct	978 ms	372416 KB	Output is correct
81	Correct	163 ms	372416 KB	Output is correct
82	Correct	146 ms	372416 KB	Output is correct
83	Correct	231 ms	372416 KB	Output is correct
84	Execution timed out	5031 ms	372416 KB	Time limit exceeded
85	Halted	0 ms	0 KB	-

답안 #60147

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 23.0 / 23.0

Subtask #5 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
23.0 / 23.0

Subtask #5
0 / 35.0

Subtask #6
0 / 20.0