답안 #60882 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60882	2018-07-24T23:27:21 Z	duality	새 집 (APIO18_new_home)	C++11	57 / 100	5000 ms	293752 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	20 ms	21496 KB	Output is correct
2	Correct	22 ms	21572 KB	Output is correct
3	Correct	22 ms	21572 KB	Output is correct
4	Correct	22 ms	21588 KB	Output is correct
5	Correct	21 ms	21644 KB	Output is correct
6	Correct	22 ms	21920 KB	Output is correct
7	Correct	22 ms	21920 KB	Output is correct
8	Correct	22 ms	21920 KB	Output is correct
9	Correct	29 ms	21920 KB	Output is correct
10	Correct	25 ms	21920 KB	Output is correct
11	Correct	24 ms	21952 KB	Output is correct
12	Correct	21 ms	21952 KB	Output is correct
13	Correct	21 ms	21952 KB	Output is correct
14	Correct	23 ms	21952 KB	Output is correct
15	Correct	21 ms	21952 KB	Output is correct
16	Correct	25 ms	21952 KB	Output is correct
17	Correct	26 ms	21952 KB	Output is correct
18	Correct	28 ms	21952 KB	Output is correct
19	Correct	30 ms	21952 KB	Output is correct
20	Correct	25 ms	21952 KB	Output is correct
21	Correct	29 ms	21952 KB	Output is correct
22	Correct	30 ms	21952 KB	Output is correct
23	Correct	23 ms	21952 KB	Output is correct
24	Correct	31 ms	21952 KB	Output is correct
25	Correct	28 ms	21952 KB	Output is correct
26	Correct	28 ms	21952 KB	Output is correct
27	Correct	26 ms	21952 KB	Output is correct
28	Correct	24 ms	21952 KB	Output is correct
29	Correct	22 ms	21952 KB	Output is correct
30	Correct	25 ms	21952 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	21496 KB	Output is correct
2	Correct	22 ms	21572 KB	Output is correct
3	Correct	22 ms	21572 KB	Output is correct
4	Correct	22 ms	21588 KB	Output is correct
5	Correct	21 ms	21644 KB	Output is correct
6	Correct	22 ms	21920 KB	Output is correct
7	Correct	22 ms	21920 KB	Output is correct
8	Correct	22 ms	21920 KB	Output is correct
9	Correct	29 ms	21920 KB	Output is correct
10	Correct	25 ms	21920 KB	Output is correct
11	Correct	24 ms	21952 KB	Output is correct
12	Correct	21 ms	21952 KB	Output is correct
13	Correct	21 ms	21952 KB	Output is correct
14	Correct	23 ms	21952 KB	Output is correct
15	Correct	21 ms	21952 KB	Output is correct
16	Correct	25 ms	21952 KB	Output is correct
17	Correct	26 ms	21952 KB	Output is correct
18	Correct	28 ms	21952 KB	Output is correct
19	Correct	30 ms	21952 KB	Output is correct
20	Correct	25 ms	21952 KB	Output is correct
21	Correct	29 ms	21952 KB	Output is correct
22	Correct	30 ms	21952 KB	Output is correct
23	Correct	23 ms	21952 KB	Output is correct
24	Correct	31 ms	21952 KB	Output is correct
25	Correct	28 ms	21952 KB	Output is correct
26	Correct	28 ms	21952 KB	Output is correct
27	Correct	26 ms	21952 KB	Output is correct
28	Correct	24 ms	21952 KB	Output is correct
29	Correct	22 ms	21952 KB	Output is correct
30	Correct	25 ms	21952 KB	Output is correct
31	Correct	644 ms	64576 KB	Output is correct
32	Correct	76 ms	64576 KB	Output is correct
33	Correct	619 ms	64576 KB	Output is correct
34	Correct	596 ms	64576 KB	Output is correct
35	Correct	573 ms	64576 KB	Output is correct
36	Correct	687 ms	64576 KB	Output is correct
37	Correct	408 ms	64576 KB	Output is correct
38	Correct	379 ms	64576 KB	Output is correct
39	Correct	358 ms	64576 KB	Output is correct
40	Correct	439 ms	64576 KB	Output is correct
41	Correct	570 ms	64576 KB	Output is correct
42	Correct	582 ms	64576 KB	Output is correct
43	Correct	76 ms	64576 KB	Output is correct
44	Correct	568 ms	64576 KB	Output is correct
45	Correct	530 ms	64576 KB	Output is correct
46	Correct	373 ms	64576 KB	Output is correct
47	Correct	255 ms	64576 KB	Output is correct
48	Correct	255 ms	64576 KB	Output is correct
49	Correct	320 ms	64576 KB	Output is correct
50	Correct	389 ms	64576 KB	Output is correct
51	Correct	311 ms	64576 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2361 ms	185200 KB	Output is correct
2	Correct	2484 ms	185200 KB	Output is correct
3	Correct	2198 ms	252668 KB	Output is correct
4	Correct	2219 ms	252668 KB	Output is correct
5	Correct	3575 ms	252668 KB	Output is correct
6	Correct	3128 ms	252668 KB	Output is correct
7	Correct	2013 ms	256272 KB	Output is correct
8	Correct	1895 ms	256272 KB	Output is correct
9	Correct	2085 ms	256272 KB	Output is correct
10	Correct	2192 ms	256272 KB	Output is correct
11	Correct	1540 ms	256272 KB	Output is correct
12	Correct	1517 ms	256272 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3671 ms	256272 KB	Output is correct
2	Correct	301 ms	256272 KB	Output is correct
3	Correct	3895 ms	256272 KB	Output is correct
4	Correct	3313 ms	293752 KB	Output is correct
5	Correct	3857 ms	293752 KB	Output is correct
6	Correct	4086 ms	293752 KB	Output is correct
7	Execution timed out	5050 ms	293752 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	21496 KB	Output is correct
2	Correct	22 ms	21572 KB	Output is correct
3	Correct	22 ms	21572 KB	Output is correct
4	Correct	22 ms	21588 KB	Output is correct
5	Correct	21 ms	21644 KB	Output is correct
6	Correct	22 ms	21920 KB	Output is correct
7	Correct	22 ms	21920 KB	Output is correct
8	Correct	22 ms	21920 KB	Output is correct
9	Correct	29 ms	21920 KB	Output is correct
10	Correct	25 ms	21920 KB	Output is correct
11	Correct	24 ms	21952 KB	Output is correct
12	Correct	21 ms	21952 KB	Output is correct
13	Correct	21 ms	21952 KB	Output is correct
14	Correct	23 ms	21952 KB	Output is correct
15	Correct	21 ms	21952 KB	Output is correct
16	Correct	25 ms	21952 KB	Output is correct
17	Correct	26 ms	21952 KB	Output is correct
18	Correct	28 ms	21952 KB	Output is correct
19	Correct	30 ms	21952 KB	Output is correct
20	Correct	25 ms	21952 KB	Output is correct
21	Correct	29 ms	21952 KB	Output is correct
22	Correct	30 ms	21952 KB	Output is correct
23	Correct	23 ms	21952 KB	Output is correct
24	Correct	31 ms	21952 KB	Output is correct
25	Correct	28 ms	21952 KB	Output is correct
26	Correct	28 ms	21952 KB	Output is correct
27	Correct	26 ms	21952 KB	Output is correct
28	Correct	24 ms	21952 KB	Output is correct
29	Correct	22 ms	21952 KB	Output is correct
30	Correct	25 ms	21952 KB	Output is correct
31	Correct	644 ms	64576 KB	Output is correct
32	Correct	76 ms	64576 KB	Output is correct
33	Correct	619 ms	64576 KB	Output is correct
34	Correct	596 ms	64576 KB	Output is correct
35	Correct	573 ms	64576 KB	Output is correct
36	Correct	687 ms	64576 KB	Output is correct
37	Correct	408 ms	64576 KB	Output is correct
38	Correct	379 ms	64576 KB	Output is correct
39	Correct	358 ms	64576 KB	Output is correct
40	Correct	439 ms	64576 KB	Output is correct
41	Correct	570 ms	64576 KB	Output is correct
42	Correct	582 ms	64576 KB	Output is correct
43	Correct	76 ms	64576 KB	Output is correct
44	Correct	568 ms	64576 KB	Output is correct
45	Correct	530 ms	64576 KB	Output is correct
46	Correct	373 ms	64576 KB	Output is correct
47	Correct	255 ms	64576 KB	Output is correct
48	Correct	255 ms	64576 KB	Output is correct
49	Correct	320 ms	64576 KB	Output is correct
50	Correct	389 ms	64576 KB	Output is correct
51	Correct	311 ms	64576 KB	Output is correct
52	Correct	638 ms	293752 KB	Output is correct
53	Correct	601 ms	293752 KB	Output is correct
54	Correct	609 ms	293752 KB	Output is correct
55	Correct	570 ms	293752 KB	Output is correct
56	Correct	492 ms	293752 KB	Output is correct
57	Correct	582 ms	293752 KB	Output is correct
58	Correct	696 ms	293752 KB	Output is correct
59	Correct	535 ms	293752 KB	Output is correct
60	Correct	629 ms	293752 KB	Output is correct
61	Correct	136 ms	293752 KB	Output is correct
62	Correct	619 ms	293752 KB	Output is correct
63	Correct	677 ms	293752 KB	Output is correct
64	Correct	723 ms	293752 KB	Output is correct
65	Correct	663 ms	293752 KB	Output is correct
66	Correct	532 ms	293752 KB	Output is correct
67	Correct	144 ms	293752 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	21496 KB	Output is correct
2	Correct	22 ms	21572 KB	Output is correct
3	Correct	22 ms	21572 KB	Output is correct
4	Correct	22 ms	21588 KB	Output is correct
5	Correct	21 ms	21644 KB	Output is correct
6	Correct	22 ms	21920 KB	Output is correct
7	Correct	22 ms	21920 KB	Output is correct
8	Correct	22 ms	21920 KB	Output is correct
9	Correct	29 ms	21920 KB	Output is correct
10	Correct	25 ms	21920 KB	Output is correct
11	Correct	24 ms	21952 KB	Output is correct
12	Correct	21 ms	21952 KB	Output is correct
13	Correct	21 ms	21952 KB	Output is correct
14	Correct	23 ms	21952 KB	Output is correct
15	Correct	21 ms	21952 KB	Output is correct
16	Correct	25 ms	21952 KB	Output is correct
17	Correct	26 ms	21952 KB	Output is correct
18	Correct	28 ms	21952 KB	Output is correct
19	Correct	30 ms	21952 KB	Output is correct
20	Correct	25 ms	21952 KB	Output is correct
21	Correct	29 ms	21952 KB	Output is correct
22	Correct	30 ms	21952 KB	Output is correct
23	Correct	23 ms	21952 KB	Output is correct
24	Correct	31 ms	21952 KB	Output is correct
25	Correct	28 ms	21952 KB	Output is correct
26	Correct	28 ms	21952 KB	Output is correct
27	Correct	26 ms	21952 KB	Output is correct
28	Correct	24 ms	21952 KB	Output is correct
29	Correct	22 ms	21952 KB	Output is correct
30	Correct	25 ms	21952 KB	Output is correct
31	Correct	644 ms	64576 KB	Output is correct
32	Correct	76 ms	64576 KB	Output is correct
33	Correct	619 ms	64576 KB	Output is correct
34	Correct	596 ms	64576 KB	Output is correct
35	Correct	573 ms	64576 KB	Output is correct
36	Correct	687 ms	64576 KB	Output is correct
37	Correct	408 ms	64576 KB	Output is correct
38	Correct	379 ms	64576 KB	Output is correct
39	Correct	358 ms	64576 KB	Output is correct
40	Correct	439 ms	64576 KB	Output is correct
41	Correct	570 ms	64576 KB	Output is correct
42	Correct	582 ms	64576 KB	Output is correct
43	Correct	76 ms	64576 KB	Output is correct
44	Correct	568 ms	64576 KB	Output is correct
45	Correct	530 ms	64576 KB	Output is correct
46	Correct	373 ms	64576 KB	Output is correct
47	Correct	255 ms	64576 KB	Output is correct
48	Correct	255 ms	64576 KB	Output is correct
49	Correct	320 ms	64576 KB	Output is correct
50	Correct	389 ms	64576 KB	Output is correct
51	Correct	311 ms	64576 KB	Output is correct
52	Correct	2361 ms	185200 KB	Output is correct
53	Correct	2484 ms	185200 KB	Output is correct
54	Correct	2198 ms	252668 KB	Output is correct
55	Correct	2219 ms	252668 KB	Output is correct
56	Correct	3575 ms	252668 KB	Output is correct
57	Correct	3128 ms	252668 KB	Output is correct
58	Correct	2013 ms	256272 KB	Output is correct
59	Correct	1895 ms	256272 KB	Output is correct
60	Correct	2085 ms	256272 KB	Output is correct
61	Correct	2192 ms	256272 KB	Output is correct
62	Correct	1540 ms	256272 KB	Output is correct
63	Correct	1517 ms	256272 KB	Output is correct
64	Correct	3671 ms	256272 KB	Output is correct
65	Correct	301 ms	256272 KB	Output is correct
66	Correct	3895 ms	256272 KB	Output is correct
67	Correct	3313 ms	293752 KB	Output is correct
68	Correct	3857 ms	293752 KB	Output is correct
69	Correct	4086 ms	293752 KB	Output is correct
70	Execution timed out	5050 ms	293752 KB	Time limit exceeded
71	Halted	0 ms	0 KB	-

답안 #60882

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