답안 #60883 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60883	2018-07-24T23:34:37 Z	duality	새 집 (APIO18_new_home)	C++11	57 / 100	5000 ms	293720 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 ((c=getchar()) < '0');
    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(),ae += sorted.size()+1;
    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();
    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();
    for (i = 0; i < n; i++) {
        x = readInt(),t = readInt()-1,a = readInt(),b = readInt();
        events[t].pb((event){a,x,1});
        events[t].pb((event){b+1,x,-1});
    }
    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++) {
            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)));
                it3 = M.erase(it3);
                it3 = M.insert(it3,mp(mp(it->first+events[i][j].x,it->first-events[i][j].x),events[i][j].time));
                M.insert(it3,mp(mp(events[i][j].x+it2->first,events[i][j].x-it2->first),events[i][j].time));
                S.insert(it,mp(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)));
                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)));
                it3 = M.erase(it3);
                it2--,p = mp(it->first+it2->first,it->first-it2->first);
                M.insert(it3,mp(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,3e8)));
        S.clear(),M.clear();
    }
    for (i = 0; i < q; i++) {
        l = readInt(),y = readInt();
        sorted.pb(y);
        oper.pb(mp(mp(2*l,-(i+1)),mp(y,-1)));
    }
    sort(oper.begin(),oper.end());
    sort(sorted.begin(),sorted.end());
    sorted.resize(unique(sorted.begin(),sorted.end())-sorted.begin());
    for (i = 0; i < oper.size(); i++) {
        if (oper[i].second.second == -1) {
            oper[i].second.first = lower_bound(sorted.begin(),sorted.end(),oper[i].second.first)-sorted.begin();
            query(oper[i].second.first,oper[i].first);
        }
        else {
            oper[i].second.first = lower_bound(sorted.begin(),sorted.end(),oper[i].second.first)-sorted.begin();
            oper[i].second.second = lower_bound(sorted.begin(),sorted.end(),oper[i].second.second)-sorted.begin()-1;
            if (oper[i].second.first <= oper[i].second.second) update(oper[i].second.first,oper[i].second.second,oper[i].first);
        }
    }
    for (i = 1; i < 2*sorted.size(); 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:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < events[i].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~~
new_home.cpp:152:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < oper.size(); i++) {
                 ~~^~~~~~~~~~~~~
new_home.cpp:163:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 1; i < 2*sorted.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
new_home.cpp:165: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	21368 KB	Output is correct
2	Correct	23 ms	21604 KB	Output is correct
3	Correct	22 ms	21604 KB	Output is correct
4	Correct	21 ms	21604 KB	Output is correct
5	Correct	24 ms	21640 KB	Output is correct
6	Correct	26 ms	21768 KB	Output is correct
7	Correct	26 ms	21824 KB	Output is correct
8	Correct	24 ms	21824 KB	Output is correct
9	Correct	24 ms	21824 KB	Output is correct
10	Correct	24 ms	21824 KB	Output is correct
11	Correct	23 ms	21916 KB	Output is correct
12	Correct	29 ms	21916 KB	Output is correct
13	Correct	26 ms	21928 KB	Output is correct
14	Correct	23 ms	21928 KB	Output is correct
15	Correct	31 ms	21928 KB	Output is correct
16	Correct	27 ms	21928 KB	Output is correct
17	Correct	27 ms	21928 KB	Output is correct
18	Correct	25 ms	21928 KB	Output is correct
19	Correct	23 ms	21936 KB	Output is correct
20	Correct	23 ms	21936 KB	Output is correct
21	Correct	23 ms	21936 KB	Output is correct
22	Correct	28 ms	21936 KB	Output is correct
23	Correct	27 ms	21936 KB	Output is correct
24	Correct	29 ms	21936 KB	Output is correct
25	Correct	24 ms	21936 KB	Output is correct
26	Correct	27 ms	21936 KB	Output is correct
27	Correct	25 ms	21936 KB	Output is correct
28	Correct	23 ms	21936 KB	Output is correct
29	Correct	27 ms	21936 KB	Output is correct
30	Correct	26 ms	21936 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21368 KB	Output is correct
2	Correct	23 ms	21604 KB	Output is correct
3	Correct	22 ms	21604 KB	Output is correct
4	Correct	21 ms	21604 KB	Output is correct
5	Correct	24 ms	21640 KB	Output is correct
6	Correct	26 ms	21768 KB	Output is correct
7	Correct	26 ms	21824 KB	Output is correct
8	Correct	24 ms	21824 KB	Output is correct
9	Correct	24 ms	21824 KB	Output is correct
10	Correct	24 ms	21824 KB	Output is correct
11	Correct	23 ms	21916 KB	Output is correct
12	Correct	29 ms	21916 KB	Output is correct
13	Correct	26 ms	21928 KB	Output is correct
14	Correct	23 ms	21928 KB	Output is correct
15	Correct	31 ms	21928 KB	Output is correct
16	Correct	27 ms	21928 KB	Output is correct
17	Correct	27 ms	21928 KB	Output is correct
18	Correct	25 ms	21928 KB	Output is correct
19	Correct	23 ms	21936 KB	Output is correct
20	Correct	23 ms	21936 KB	Output is correct
21	Correct	23 ms	21936 KB	Output is correct
22	Correct	28 ms	21936 KB	Output is correct
23	Correct	27 ms	21936 KB	Output is correct
24	Correct	29 ms	21936 KB	Output is correct
25	Correct	24 ms	21936 KB	Output is correct
26	Correct	27 ms	21936 KB	Output is correct
27	Correct	25 ms	21936 KB	Output is correct
28	Correct	23 ms	21936 KB	Output is correct
29	Correct	27 ms	21936 KB	Output is correct
30	Correct	26 ms	21936 KB	Output is correct
31	Correct	714 ms	64660 KB	Output is correct
32	Correct	77 ms	64660 KB	Output is correct
33	Correct	644 ms	64660 KB	Output is correct
34	Correct	745 ms	64660 KB	Output is correct
35	Correct	746 ms	64660 KB	Output is correct
36	Correct	686 ms	64660 KB	Output is correct
37	Correct	551 ms	64660 KB	Output is correct
38	Correct	599 ms	64660 KB	Output is correct
39	Correct	343 ms	64660 KB	Output is correct
40	Correct	398 ms	64660 KB	Output is correct
41	Correct	741 ms	64660 KB	Output is correct
42	Correct	623 ms	64660 KB	Output is correct
43	Correct	72 ms	64660 KB	Output is correct
44	Correct	617 ms	64660 KB	Output is correct
45	Correct	479 ms	64660 KB	Output is correct
46	Correct	399 ms	64660 KB	Output is correct
47	Correct	300 ms	64660 KB	Output is correct
48	Correct	272 ms	64660 KB	Output is correct
49	Correct	356 ms	64660 KB	Output is correct
50	Correct	405 ms	64660 KB	Output is correct
51	Correct	292 ms	64660 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2328 ms	185236 KB	Output is correct
2	Correct	3080 ms	185236 KB	Output is correct
3	Correct	2910 ms	252748 KB	Output is correct
4	Correct	2125 ms	252748 KB	Output is correct
5	Correct	3694 ms	252748 KB	Output is correct
6	Correct	3281 ms	252748 KB	Output is correct
7	Correct	2499 ms	256224 KB	Output is correct
8	Correct	2388 ms	256224 KB	Output is correct
9	Correct	2372 ms	256224 KB	Output is correct
10	Correct	2357 ms	256224 KB	Output is correct
11	Correct	1507 ms	256224 KB	Output is correct
12	Correct	1640 ms	256224 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3804 ms	256224 KB	Output is correct
2	Correct	268 ms	256224 KB	Output is correct
3	Correct	4130 ms	256224 KB	Output is correct
4	Correct	3507 ms	293720 KB	Output is correct
5	Correct	3943 ms	293720 KB	Output is correct
6	Correct	4005 ms	293720 KB	Output is correct
7	Execution timed out	5051 ms	293720 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21368 KB	Output is correct
2	Correct	23 ms	21604 KB	Output is correct
3	Correct	22 ms	21604 KB	Output is correct
4	Correct	21 ms	21604 KB	Output is correct
5	Correct	24 ms	21640 KB	Output is correct
6	Correct	26 ms	21768 KB	Output is correct
7	Correct	26 ms	21824 KB	Output is correct
8	Correct	24 ms	21824 KB	Output is correct
9	Correct	24 ms	21824 KB	Output is correct
10	Correct	24 ms	21824 KB	Output is correct
11	Correct	23 ms	21916 KB	Output is correct
12	Correct	29 ms	21916 KB	Output is correct
13	Correct	26 ms	21928 KB	Output is correct
14	Correct	23 ms	21928 KB	Output is correct
15	Correct	31 ms	21928 KB	Output is correct
16	Correct	27 ms	21928 KB	Output is correct
17	Correct	27 ms	21928 KB	Output is correct
18	Correct	25 ms	21928 KB	Output is correct
19	Correct	23 ms	21936 KB	Output is correct
20	Correct	23 ms	21936 KB	Output is correct
21	Correct	23 ms	21936 KB	Output is correct
22	Correct	28 ms	21936 KB	Output is correct
23	Correct	27 ms	21936 KB	Output is correct
24	Correct	29 ms	21936 KB	Output is correct
25	Correct	24 ms	21936 KB	Output is correct
26	Correct	27 ms	21936 KB	Output is correct
27	Correct	25 ms	21936 KB	Output is correct
28	Correct	23 ms	21936 KB	Output is correct
29	Correct	27 ms	21936 KB	Output is correct
30	Correct	26 ms	21936 KB	Output is correct
31	Correct	714 ms	64660 KB	Output is correct
32	Correct	77 ms	64660 KB	Output is correct
33	Correct	644 ms	64660 KB	Output is correct
34	Correct	745 ms	64660 KB	Output is correct
35	Correct	746 ms	64660 KB	Output is correct
36	Correct	686 ms	64660 KB	Output is correct
37	Correct	551 ms	64660 KB	Output is correct
38	Correct	599 ms	64660 KB	Output is correct
39	Correct	343 ms	64660 KB	Output is correct
40	Correct	398 ms	64660 KB	Output is correct
41	Correct	741 ms	64660 KB	Output is correct
42	Correct	623 ms	64660 KB	Output is correct
43	Correct	72 ms	64660 KB	Output is correct
44	Correct	617 ms	64660 KB	Output is correct
45	Correct	479 ms	64660 KB	Output is correct
46	Correct	399 ms	64660 KB	Output is correct
47	Correct	300 ms	64660 KB	Output is correct
48	Correct	272 ms	64660 KB	Output is correct
49	Correct	356 ms	64660 KB	Output is correct
50	Correct	405 ms	64660 KB	Output is correct
51	Correct	292 ms	64660 KB	Output is correct
52	Correct	682 ms	293720 KB	Output is correct
53	Correct	610 ms	293720 KB	Output is correct
54	Correct	594 ms	293720 KB	Output is correct
55	Correct	490 ms	293720 KB	Output is correct
56	Correct	458 ms	293720 KB	Output is correct
57	Correct	493 ms	293720 KB	Output is correct
58	Correct	605 ms	293720 KB	Output is correct
59	Correct	553 ms	293720 KB	Output is correct
60	Correct	698 ms	293720 KB	Output is correct
61	Correct	166 ms	293720 KB	Output is correct
62	Correct	703 ms	293720 KB	Output is correct
63	Correct	664 ms	293720 KB	Output is correct
64	Correct	668 ms	293720 KB	Output is correct
65	Correct	740 ms	293720 KB	Output is correct
66	Correct	654 ms	293720 KB	Output is correct
67	Correct	175 ms	293720 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21368 KB	Output is correct
2	Correct	23 ms	21604 KB	Output is correct
3	Correct	22 ms	21604 KB	Output is correct
4	Correct	21 ms	21604 KB	Output is correct
5	Correct	24 ms	21640 KB	Output is correct
6	Correct	26 ms	21768 KB	Output is correct
7	Correct	26 ms	21824 KB	Output is correct
8	Correct	24 ms	21824 KB	Output is correct
9	Correct	24 ms	21824 KB	Output is correct
10	Correct	24 ms	21824 KB	Output is correct
11	Correct	23 ms	21916 KB	Output is correct
12	Correct	29 ms	21916 KB	Output is correct
13	Correct	26 ms	21928 KB	Output is correct
14	Correct	23 ms	21928 KB	Output is correct
15	Correct	31 ms	21928 KB	Output is correct
16	Correct	27 ms	21928 KB	Output is correct
17	Correct	27 ms	21928 KB	Output is correct
18	Correct	25 ms	21928 KB	Output is correct
19	Correct	23 ms	21936 KB	Output is correct
20	Correct	23 ms	21936 KB	Output is correct
21	Correct	23 ms	21936 KB	Output is correct
22	Correct	28 ms	21936 KB	Output is correct
23	Correct	27 ms	21936 KB	Output is correct
24	Correct	29 ms	21936 KB	Output is correct
25	Correct	24 ms	21936 KB	Output is correct
26	Correct	27 ms	21936 KB	Output is correct
27	Correct	25 ms	21936 KB	Output is correct
28	Correct	23 ms	21936 KB	Output is correct
29	Correct	27 ms	21936 KB	Output is correct
30	Correct	26 ms	21936 KB	Output is correct
31	Correct	714 ms	64660 KB	Output is correct
32	Correct	77 ms	64660 KB	Output is correct
33	Correct	644 ms	64660 KB	Output is correct
34	Correct	745 ms	64660 KB	Output is correct
35	Correct	746 ms	64660 KB	Output is correct
36	Correct	686 ms	64660 KB	Output is correct
37	Correct	551 ms	64660 KB	Output is correct
38	Correct	599 ms	64660 KB	Output is correct
39	Correct	343 ms	64660 KB	Output is correct
40	Correct	398 ms	64660 KB	Output is correct
41	Correct	741 ms	64660 KB	Output is correct
42	Correct	623 ms	64660 KB	Output is correct
43	Correct	72 ms	64660 KB	Output is correct
44	Correct	617 ms	64660 KB	Output is correct
45	Correct	479 ms	64660 KB	Output is correct
46	Correct	399 ms	64660 KB	Output is correct
47	Correct	300 ms	64660 KB	Output is correct
48	Correct	272 ms	64660 KB	Output is correct
49	Correct	356 ms	64660 KB	Output is correct
50	Correct	405 ms	64660 KB	Output is correct
51	Correct	292 ms	64660 KB	Output is correct
52	Correct	2328 ms	185236 KB	Output is correct
53	Correct	3080 ms	185236 KB	Output is correct
54	Correct	2910 ms	252748 KB	Output is correct
55	Correct	2125 ms	252748 KB	Output is correct
56	Correct	3694 ms	252748 KB	Output is correct
57	Correct	3281 ms	252748 KB	Output is correct
58	Correct	2499 ms	256224 KB	Output is correct
59	Correct	2388 ms	256224 KB	Output is correct
60	Correct	2372 ms	256224 KB	Output is correct
61	Correct	2357 ms	256224 KB	Output is correct
62	Correct	1507 ms	256224 KB	Output is correct
63	Correct	1640 ms	256224 KB	Output is correct
64	Correct	3804 ms	256224 KB	Output is correct
65	Correct	268 ms	256224 KB	Output is correct
66	Correct	4130 ms	256224 KB	Output is correct
67	Correct	3507 ms	293720 KB	Output is correct
68	Correct	3943 ms	293720 KB	Output is correct
69	Correct	4005 ms	293720 KB	Output is correct
70	Execution timed out	5051 ms	293720 KB	Time limit exceeded
71	Halted	0 ms	0 KB	-

답안 #60883

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