답안 #60857 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60857	2018-07-24T21:12:20 Z	duality	새 집 (APIO18_new_home)	C++11	80 / 100	4686 ms	336320 KB

new_home

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
int readInt() {
    char c;
    while (isspace(c=getchar()));
    int n = c-'0';
    while ((c=getchar()) >= '0') n *= 10,n += c-'0';
    return n;
}

struct event { int time,x,t; };
bool comp(event a,event b) {
    if (a.time == b.time) return a.t < b.t;
    else return a.time < b.time;
}
vi sorted;
vector<event> events[300000];
map<int,int> S;
map<pii,int> M;
vector<pair<pii,pii> > oper;
vpii tree[600000];
int ans[300000];
int update(int as,int ae,pii p) {
    as += sorted.size()-1,ae += sorted.size();
    while (as < ae) {
        if (as & 1) tree[as++].pb(p);
        if (ae & 1) tree[--ae].pb(p);
        as >>= 1,ae >>= 1;
    }
    return 0;
}
int query(int q,pii p) {
    q += sorted.size()-1;
    while (q > 0) tree[q].pb(p),q >>= 1;
    return 0;
}
int main() {
    int i,j;
    int n,k,q;
    int x,t,a,b,l,y;
    n = readInt(),k = readInt(),q = readInt();
    //scanf("%d %d %d",&n,&k,&q);
    sorted.pb(0),sorted.pb(3e8);
    for (i = 0; i < n; i++) {
        //scanf("%d %d %d %d",&x,&t,&a,&b),t--;
        x = readInt(),t = readInt()-1,a = readInt(),b = readInt();
        events[t].pb((event){a,x,1});
        events[t].pb((event){b+1,x,-1});
        sorted.pb(a),sorted.pb(b+1);
    }
    sort(sorted.begin(),sorted.end());
    sorted.resize(unique(sorted.begin(),sorted.end())-sorted.begin());
    for (i = 0; i < k; i++) {
        sort(events[i].begin(),events[i].end(),comp);
        S[-3e8] = S[3e8] = 1,M[mp(0,6e8)] = 0;
        for (j = 0; j < events[i].size(); j++) {
            events[i][j].time = lower_bound(sorted.begin(),sorted.end(),events[i][j].time)-sorted.begin();
            if (events[i][j].t == 1) {
                auto it = S.lower_bound(events[i][j].x);
                if (it->first == events[i][j].x) {
                    it->second++;
                    continue;
                }
                auto it2 = it;
                it2--;
                pii p = mp(it->first+it2->first,it->first-it2->first);
                auto it3 = M.find(p);
                oper.pb(mp(p,mp(it3->second,events[i][j].time-1)));
                M.erase(it3);
                M[mp(it->first+events[i][j].x,it->first-events[i][j].x)] = events[i][j].time;
                M[mp(events[i][j].x+it2->first,events[i][j].x-it2->first)] = events[i][j].time;
                S[events[i][j].x] = 1;
            }
            else {
                auto it = S.find(events[i][j].x);
                if (it->second > 1) {
                    it->second--;
                    continue;
                }
                auto it2 = it;
                it2--;
                pii p = mp(it->first+it2->first,it->first-it2->first);
                auto it3 = M.find(p);
                oper.pb(mp(p,mp(it3->second,events[i][j].time-1)));
                it3 = M.erase(it3);
                it++,it2++,p = mp(it->first+it2->first,it->first-it2->first);
                oper.pb(mp(p,mp(it3->second,events[i][j].time-1)));
                M.erase(it3);
                it2--,p = mp(it->first+it2->first,it->first-it2->first);
                M[p] = events[i][j].time;
                S.erase(--it);
            }
        }
        for (auto it = M.begin(); it != M.end(); it++) oper.pb(mp(it->first,mp(it->second,sorted.size()-2)));
        S.clear(),M.clear();
    }
    for (i = 0; i < q; i++) {
        l = readInt(),y = readInt();
        //scanf("%d %d",&l,&y);
        int p = upper_bound(sorted.begin(),sorted.end(),y)-sorted.begin()-1;
        oper.pb(mp(mp(2*l,-(i+1)),mp(p,-1)));
    }
    sort(oper.begin(),oper.end());
    for (i = 0; i < oper.size(); i++) {
        if (oper[i].second.second == -1) query(oper[i].second.first,oper[i].first);
        else update(oper[i].second.first,oper[i].second.second,oper[i].first);
    }
    for (i = 1; i < 2*(sorted.size()-1); i++) {
        pii m = mp(-3e8,0);
        for (j = 0; j < tree[i].size(); j++) {
            if (tree[i][j].second >= 0) {
                if (tree[i][j].second > m.second-(tree[i][j].first-m.first)) m = tree[i][j];
            }
            else ans[-tree[i][j].second-1] = max(ans[-tree[i][j].second-1],m.second-(tree[i][j].first-m.first));
        }
        m = mp(3e8,0);
        for (j = tree[i].size()-1; j >= 0; j--) {
            if (tree[i][j].second >= 0) {
                if (tree[i][j].second > m.second-(m.first-tree[i][j].first)) m = tree[i][j];
            }
            else ans[-tree[i][j].second-1] = max(ans[-tree[i][j].second-1],m.second-(m.first-tree[i][j].first));
        }
    }
    for (i = 0; i < q; i++) printf("%d\n",(ans[i] > 3e8) ? -1:ans[i]/2);

    return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < events[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~
new_home.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < oper.size(); i++) {
                 ~~^~~~~~~~~~~~~
new_home.cpp:162:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < 2*(sorted.size()-1); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp:164:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < tree[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21496 KB	Output is correct
2	Correct	21 ms	21496 KB	Output is correct
3	Correct	22 ms	21668 KB	Output is correct
4	Correct	21 ms	21668 KB	Output is correct
5	Correct	23 ms	21672 KB	Output is correct
6	Correct	25 ms	21872 KB	Output is correct
7	Correct	30 ms	21988 KB	Output is correct
8	Correct	29 ms	22136 KB	Output is correct
9	Correct	32 ms	22136 KB	Output is correct
10	Correct	27 ms	22136 KB	Output is correct
11	Correct	22 ms	22136 KB	Output is correct
12	Correct	21 ms	22136 KB	Output is correct
13	Correct	23 ms	22136 KB	Output is correct
14	Correct	27 ms	22136 KB	Output is correct
15	Correct	24 ms	22136 KB	Output is correct
16	Correct	23 ms	22136 KB	Output is correct
17	Correct	22 ms	22136 KB	Output is correct
18	Correct	31 ms	22136 KB	Output is correct
19	Correct	23 ms	22136 KB	Output is correct
20	Correct	23 ms	22136 KB	Output is correct
21	Correct	26 ms	22136 KB	Output is correct
22	Correct	24 ms	22136 KB	Output is correct
23	Correct	22 ms	22136 KB	Output is correct
24	Correct	22 ms	22136 KB	Output is correct
25	Correct	22 ms	22136 KB	Output is correct
26	Correct	29 ms	22136 KB	Output is correct
27	Correct	25 ms	22136 KB	Output is correct
28	Correct	23 ms	22136 KB	Output is correct
29	Correct	23 ms	22136 KB	Output is correct
30	Correct	27 ms	22136 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21496 KB	Output is correct
2	Correct	21 ms	21496 KB	Output is correct
3	Correct	22 ms	21668 KB	Output is correct
4	Correct	21 ms	21668 KB	Output is correct
5	Correct	23 ms	21672 KB	Output is correct
6	Correct	25 ms	21872 KB	Output is correct
7	Correct	30 ms	21988 KB	Output is correct
8	Correct	29 ms	22136 KB	Output is correct
9	Correct	32 ms	22136 KB	Output is correct
10	Correct	27 ms	22136 KB	Output is correct
11	Correct	22 ms	22136 KB	Output is correct
12	Correct	21 ms	22136 KB	Output is correct
13	Correct	23 ms	22136 KB	Output is correct
14	Correct	27 ms	22136 KB	Output is correct
15	Correct	24 ms	22136 KB	Output is correct
16	Correct	23 ms	22136 KB	Output is correct
17	Correct	22 ms	22136 KB	Output is correct
18	Correct	31 ms	22136 KB	Output is correct
19	Correct	23 ms	22136 KB	Output is correct
20	Correct	23 ms	22136 KB	Output is correct
21	Correct	26 ms	22136 KB	Output is correct
22	Correct	24 ms	22136 KB	Output is correct
23	Correct	22 ms	22136 KB	Output is correct
24	Correct	22 ms	22136 KB	Output is correct
25	Correct	22 ms	22136 KB	Output is correct
26	Correct	29 ms	22136 KB	Output is correct
27	Correct	25 ms	22136 KB	Output is correct
28	Correct	23 ms	22136 KB	Output is correct
29	Correct	23 ms	22136 KB	Output is correct
30	Correct	27 ms	22136 KB	Output is correct
31	Correct	744 ms	71108 KB	Output is correct
32	Correct	75 ms	71108 KB	Output is correct
33	Correct	631 ms	71108 KB	Output is correct
34	Correct	710 ms	71108 KB	Output is correct
35	Correct	720 ms	71108 KB	Output is correct
36	Correct	664 ms	71108 KB	Output is correct
37	Correct	560 ms	71108 KB	Output is correct
38	Correct	633 ms	71108 KB	Output is correct
39	Correct	426 ms	71108 KB	Output is correct
40	Correct	408 ms	71108 KB	Output is correct
41	Correct	717 ms	71108 KB	Output is correct
42	Correct	739 ms	73512 KB	Output is correct
43	Correct	100 ms	73512 KB	Output is correct
44	Correct	625 ms	73512 KB	Output is correct
45	Correct	551 ms	73512 KB	Output is correct
46	Correct	632 ms	73512 KB	Output is correct
47	Correct	353 ms	73512 KB	Output is correct
48	Correct	332 ms	73512 KB	Output is correct
49	Correct	461 ms	73512 KB	Output is correct
50	Correct	411 ms	73512 KB	Output is correct
51	Correct	378 ms	73512 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	966 ms	93732 KB	Output is correct
2	Correct	1486 ms	93732 KB	Output is correct
3	Correct	843 ms	99736 KB	Output is correct
4	Correct	876 ms	99736 KB	Output is correct
5	Correct	2325 ms	101012 KB	Output is correct
6	Correct	1703 ms	101012 KB	Output is correct
7	Correct	632 ms	101012 KB	Output is correct
8	Correct	694 ms	101012 KB	Output is correct
9	Correct	734 ms	101012 KB	Output is correct
10	Correct	954 ms	101012 KB	Output is correct
11	Correct	1031 ms	101012 KB	Output is correct
12	Correct	845 ms	101012 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3435 ms	238888 KB	Output is correct
2	Correct	328 ms	238888 KB	Output is correct
3	Correct	3968 ms	238888 KB	Output is correct
4	Correct	3317 ms	312512 KB	Output is correct
5	Correct	3833 ms	312512 KB	Output is correct
6	Correct	2957 ms	312512 KB	Output is correct
7	Correct	4596 ms	312512 KB	Output is correct
8	Correct	4686 ms	312512 KB	Output is correct
9	Correct	2309 ms	328524 KB	Output is correct
10	Correct	2749 ms	328524 KB	Output is correct
11	Correct	2930 ms	328524 KB	Output is correct
12	Correct	3413 ms	328524 KB	Output is correct
13	Correct	1962 ms	328524 KB	Output is correct
14	Correct	1707 ms	328524 KB	Output is correct
15	Correct	1792 ms	328524 KB	Output is correct
16	Correct	1763 ms	336320 KB	Output is correct
17	Correct	2378 ms	336320 KB	Output is correct

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21496 KB	Output is correct
2	Correct	21 ms	21496 KB	Output is correct
3	Correct	22 ms	21668 KB	Output is correct
4	Correct	21 ms	21668 KB	Output is correct
5	Correct	23 ms	21672 KB	Output is correct
6	Correct	25 ms	21872 KB	Output is correct
7	Correct	30 ms	21988 KB	Output is correct
8	Correct	29 ms	22136 KB	Output is correct
9	Correct	32 ms	22136 KB	Output is correct
10	Correct	27 ms	22136 KB	Output is correct
11	Correct	22 ms	22136 KB	Output is correct
12	Correct	21 ms	22136 KB	Output is correct
13	Correct	23 ms	22136 KB	Output is correct
14	Correct	27 ms	22136 KB	Output is correct
15	Correct	24 ms	22136 KB	Output is correct
16	Correct	23 ms	22136 KB	Output is correct
17	Correct	22 ms	22136 KB	Output is correct
18	Correct	31 ms	22136 KB	Output is correct
19	Correct	23 ms	22136 KB	Output is correct
20	Correct	23 ms	22136 KB	Output is correct
21	Correct	26 ms	22136 KB	Output is correct
22	Correct	24 ms	22136 KB	Output is correct
23	Correct	22 ms	22136 KB	Output is correct
24	Correct	22 ms	22136 KB	Output is correct
25	Correct	22 ms	22136 KB	Output is correct
26	Correct	29 ms	22136 KB	Output is correct
27	Correct	25 ms	22136 KB	Output is correct
28	Correct	23 ms	22136 KB	Output is correct
29	Correct	23 ms	22136 KB	Output is correct
30	Correct	27 ms	22136 KB	Output is correct
31	Correct	744 ms	71108 KB	Output is correct
32	Correct	75 ms	71108 KB	Output is correct
33	Correct	631 ms	71108 KB	Output is correct
34	Correct	710 ms	71108 KB	Output is correct
35	Correct	720 ms	71108 KB	Output is correct
36	Correct	664 ms	71108 KB	Output is correct
37	Correct	560 ms	71108 KB	Output is correct
38	Correct	633 ms	71108 KB	Output is correct
39	Correct	426 ms	71108 KB	Output is correct
40	Correct	408 ms	71108 KB	Output is correct
41	Correct	717 ms	71108 KB	Output is correct
42	Correct	739 ms	73512 KB	Output is correct
43	Correct	100 ms	73512 KB	Output is correct
44	Correct	625 ms	73512 KB	Output is correct
45	Correct	551 ms	73512 KB	Output is correct
46	Correct	632 ms	73512 KB	Output is correct
47	Correct	353 ms	73512 KB	Output is correct
48	Correct	332 ms	73512 KB	Output is correct
49	Correct	461 ms	73512 KB	Output is correct
50	Correct	411 ms	73512 KB	Output is correct
51	Correct	378 ms	73512 KB	Output is correct
52	Correct	748 ms	336320 KB	Output is correct
53	Correct	808 ms	336320 KB	Output is correct
54	Correct	909 ms	336320 KB	Output is correct
55	Correct	620 ms	336320 KB	Output is correct
56	Correct	577 ms	336320 KB	Output is correct
57	Correct	681 ms	336320 KB	Output is correct
58	Correct	813 ms	336320 KB	Output is correct
59	Correct	694 ms	336320 KB	Output is correct
60	Correct	780 ms	336320 KB	Output is correct
61	Correct	152 ms	336320 KB	Output is correct
62	Correct	734 ms	336320 KB	Output is correct
63	Correct	819 ms	336320 KB	Output is correct
64	Correct	729 ms	336320 KB	Output is correct
65	Correct	743 ms	336320 KB	Output is correct
66	Correct	667 ms	336320 KB	Output is correct
67	Correct	149 ms	336320 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21496 KB	Output is correct
2	Correct	21 ms	21496 KB	Output is correct
3	Correct	22 ms	21668 KB	Output is correct
4	Correct	21 ms	21668 KB	Output is correct
5	Correct	23 ms	21672 KB	Output is correct
6	Correct	25 ms	21872 KB	Output is correct
7	Correct	30 ms	21988 KB	Output is correct
8	Correct	29 ms	22136 KB	Output is correct
9	Correct	32 ms	22136 KB	Output is correct
10	Correct	27 ms	22136 KB	Output is correct
11	Correct	22 ms	22136 KB	Output is correct
12	Correct	21 ms	22136 KB	Output is correct
13	Correct	23 ms	22136 KB	Output is correct
14	Correct	27 ms	22136 KB	Output is correct
15	Correct	24 ms	22136 KB	Output is correct
16	Correct	23 ms	22136 KB	Output is correct
17	Correct	22 ms	22136 KB	Output is correct
18	Correct	31 ms	22136 KB	Output is correct
19	Correct	23 ms	22136 KB	Output is correct
20	Correct	23 ms	22136 KB	Output is correct
21	Correct	26 ms	22136 KB	Output is correct
22	Correct	24 ms	22136 KB	Output is correct
23	Correct	22 ms	22136 KB	Output is correct
24	Correct	22 ms	22136 KB	Output is correct
25	Correct	22 ms	22136 KB	Output is correct
26	Correct	29 ms	22136 KB	Output is correct
27	Correct	25 ms	22136 KB	Output is correct
28	Correct	23 ms	22136 KB	Output is correct
29	Correct	23 ms	22136 KB	Output is correct
30	Correct	27 ms	22136 KB	Output is correct
31	Correct	744 ms	71108 KB	Output is correct
32	Correct	75 ms	71108 KB	Output is correct
33	Correct	631 ms	71108 KB	Output is correct
34	Correct	710 ms	71108 KB	Output is correct
35	Correct	720 ms	71108 KB	Output is correct
36	Correct	664 ms	71108 KB	Output is correct
37	Correct	560 ms	71108 KB	Output is correct
38	Correct	633 ms	71108 KB	Output is correct
39	Correct	426 ms	71108 KB	Output is correct
40	Correct	408 ms	71108 KB	Output is correct
41	Correct	717 ms	71108 KB	Output is correct
42	Correct	739 ms	73512 KB	Output is correct
43	Correct	100 ms	73512 KB	Output is correct
44	Correct	625 ms	73512 KB	Output is correct
45	Correct	551 ms	73512 KB	Output is correct
46	Correct	632 ms	73512 KB	Output is correct
47	Correct	353 ms	73512 KB	Output is correct
48	Correct	332 ms	73512 KB	Output is correct
49	Correct	461 ms	73512 KB	Output is correct
50	Correct	411 ms	73512 KB	Output is correct
51	Correct	378 ms	73512 KB	Output is correct
52	Correct	966 ms	93732 KB	Output is correct
53	Correct	1486 ms	93732 KB	Output is correct
54	Correct	843 ms	99736 KB	Output is correct
55	Correct	876 ms	99736 KB	Output is correct
56	Correct	2325 ms	101012 KB	Output is correct
57	Correct	1703 ms	101012 KB	Output is correct
58	Correct	632 ms	101012 KB	Output is correct
59	Correct	694 ms	101012 KB	Output is correct
60	Correct	734 ms	101012 KB	Output is correct
61	Correct	954 ms	101012 KB	Output is correct
62	Correct	1031 ms	101012 KB	Output is correct
63	Correct	845 ms	101012 KB	Output is correct
64	Correct	3435 ms	238888 KB	Output is correct
65	Correct	328 ms	238888 KB	Output is correct
66	Correct	3968 ms	238888 KB	Output is correct
67	Correct	3317 ms	312512 KB	Output is correct
68	Correct	3833 ms	312512 KB	Output is correct
69	Correct	2957 ms	312512 KB	Output is correct
70	Correct	4596 ms	312512 KB	Output is correct
71	Correct	4686 ms	312512 KB	Output is correct
72	Correct	2309 ms	328524 KB	Output is correct
73	Correct	2749 ms	328524 KB	Output is correct
74	Correct	2930 ms	328524 KB	Output is correct
75	Correct	3413 ms	328524 KB	Output is correct
76	Correct	1962 ms	328524 KB	Output is correct
77	Correct	1707 ms	328524 KB	Output is correct
78	Correct	1792 ms	328524 KB	Output is correct
79	Correct	1763 ms	336320 KB	Output is correct
80	Correct	2378 ms	336320 KB	Output is correct
81	Correct	748 ms	336320 KB	Output is correct
82	Correct	808 ms	336320 KB	Output is correct
83	Correct	909 ms	336320 KB	Output is correct
84	Correct	620 ms	336320 KB	Output is correct
85	Correct	577 ms	336320 KB	Output is correct
86	Correct	681 ms	336320 KB	Output is correct
87	Correct	813 ms	336320 KB	Output is correct
88	Correct	694 ms	336320 KB	Output is correct
89	Correct	780 ms	336320 KB	Output is correct
90	Correct	152 ms	336320 KB	Output is correct
91	Correct	734 ms	336320 KB	Output is correct
92	Correct	819 ms	336320 KB	Output is correct
93	Correct	729 ms	336320 KB	Output is correct
94	Correct	743 ms	336320 KB	Output is correct
95	Correct	667 ms	336320 KB	Output is correct
96	Correct	149 ms	336320 KB	Output is correct
97	Runtime error	1288 ms	336320 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
98	Halted	0 ms	0 KB	-

답안 #60857

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 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
23.0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0