답안 #60890 :: oj.uz

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21496 KB	Output is correct
2	Correct	20 ms	21496 KB	Output is correct
3	Correct	22 ms	21540 KB	Output is correct
4	Correct	23 ms	21568 KB	Output is correct
5	Correct	22 ms	21696 KB	Output is correct
6	Correct	25 ms	21728 KB	Output is correct
7	Correct	22 ms	21900 KB	Output is correct
8	Correct	22 ms	21900 KB	Output is correct
9	Correct	23 ms	21952 KB	Output is correct
10	Correct	23 ms	21952 KB	Output is correct
11	Correct	31 ms	21952 KB	Output is correct
12	Correct	27 ms	21952 KB	Output is correct
13	Correct	22 ms	21952 KB	Output is correct
14	Correct	24 ms	21952 KB	Output is correct
15	Correct	22 ms	21952 KB	Output is correct
16	Correct	23 ms	21952 KB	Output is correct
17	Correct	23 ms	21952 KB	Output is correct
18	Correct	28 ms	21952 KB	Output is correct
19	Correct	23 ms	21952 KB	Output is correct
20	Correct	24 ms	21952 KB	Output is correct
21	Correct	22 ms	21952 KB	Output is correct
22	Correct	32 ms	21952 KB	Output is correct
23	Correct	31 ms	21952 KB	Output is correct
24	Correct	23 ms	21952 KB	Output is correct
25	Correct	23 ms	21952 KB	Output is correct
26	Correct	27 ms	21952 KB	Output is correct
27	Correct	27 ms	21952 KB	Output is correct
28	Correct	27 ms	21952 KB	Output is correct
29	Correct	27 ms	21952 KB	Output is correct
30	Correct	29 ms	21952 KB	Output is correct
31	Correct	739 ms	64568 KB	Output is correct
32	Correct	76 ms	64568 KB	Output is correct
33	Correct	691 ms	64568 KB	Output is correct
34	Correct	733 ms	64568 KB	Output is correct
35	Correct	676 ms	64568 KB	Output is correct
36	Correct	644 ms	64568 KB	Output is correct
37	Correct	482 ms	64568 KB	Output is correct
38	Correct	430 ms	64568 KB	Output is correct
39	Correct	382 ms	64568 KB	Output is correct
40	Correct	350 ms	64568 KB	Output is correct
41	Correct	577 ms	64568 KB	Output is correct
42	Correct	615 ms	64568 KB	Output is correct
43	Correct	93 ms	64568 KB	Output is correct
44	Correct	703 ms	64568 KB	Output is correct
45	Correct	658 ms	64568 KB	Output is correct
46	Correct	564 ms	64568 KB	Output is correct
47	Correct	344 ms	64568 KB	Output is correct
48	Correct	312 ms	64568 KB	Output is correct
49	Correct	325 ms	64568 KB	Output is correct
50	Correct	413 ms	64568 KB	Output is correct
51	Correct	365 ms	64568 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2734 ms	185112 KB	Output is correct
2	Correct	3644 ms	185112 KB	Output is correct
3	Correct	2891 ms	252748 KB	Output is correct
4	Correct	2782 ms	252748 KB	Output is correct
5	Correct	4645 ms	252748 KB	Output is correct
6	Correct	3861 ms	252748 KB	Output is correct
7	Correct	2768 ms	256260 KB	Output is correct
8	Correct	2652 ms	256260 KB	Output is correct
9	Correct	2761 ms	256260 KB	Output is correct
10	Correct	2881 ms	256260 KB	Output is correct
11	Correct	1987 ms	256260 KB	Output is correct
12	Correct	2104 ms	256260 KB	Output is correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4644 ms	256260 KB	Output is correct
2	Correct	360 ms	256260 KB	Output is correct
3	Execution timed out	5017 ms	256260 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21496 KB	Output is correct
2	Correct	20 ms	21496 KB	Output is correct
3	Correct	22 ms	21540 KB	Output is correct
4	Correct	23 ms	21568 KB	Output is correct
5	Correct	22 ms	21696 KB	Output is correct
6	Correct	25 ms	21728 KB	Output is correct
7	Correct	22 ms	21900 KB	Output is correct
8	Correct	22 ms	21900 KB	Output is correct
9	Correct	23 ms	21952 KB	Output is correct
10	Correct	23 ms	21952 KB	Output is correct
11	Correct	31 ms	21952 KB	Output is correct
12	Correct	27 ms	21952 KB	Output is correct
13	Correct	22 ms	21952 KB	Output is correct
14	Correct	24 ms	21952 KB	Output is correct
15	Correct	22 ms	21952 KB	Output is correct
16	Correct	23 ms	21952 KB	Output is correct
17	Correct	23 ms	21952 KB	Output is correct
18	Correct	28 ms	21952 KB	Output is correct
19	Correct	23 ms	21952 KB	Output is correct
20	Correct	24 ms	21952 KB	Output is correct
21	Correct	22 ms	21952 KB	Output is correct
22	Correct	32 ms	21952 KB	Output is correct
23	Correct	31 ms	21952 KB	Output is correct
24	Correct	23 ms	21952 KB	Output is correct
25	Correct	23 ms	21952 KB	Output is correct
26	Correct	27 ms	21952 KB	Output is correct
27	Correct	27 ms	21952 KB	Output is correct
28	Correct	27 ms	21952 KB	Output is correct
29	Correct	27 ms	21952 KB	Output is correct
30	Correct	29 ms	21952 KB	Output is correct
31	Correct	739 ms	64568 KB	Output is correct
32	Correct	76 ms	64568 KB	Output is correct
33	Correct	691 ms	64568 KB	Output is correct
34	Correct	733 ms	64568 KB	Output is correct
35	Correct	676 ms	64568 KB	Output is correct
36	Correct	644 ms	64568 KB	Output is correct
37	Correct	482 ms	64568 KB	Output is correct
38	Correct	430 ms	64568 KB	Output is correct
39	Correct	382 ms	64568 KB	Output is correct
40	Correct	350 ms	64568 KB	Output is correct
41	Correct	577 ms	64568 KB	Output is correct
42	Correct	615 ms	64568 KB	Output is correct
43	Correct	93 ms	64568 KB	Output is correct
44	Correct	703 ms	64568 KB	Output is correct
45	Correct	658 ms	64568 KB	Output is correct
46	Correct	564 ms	64568 KB	Output is correct
47	Correct	344 ms	64568 KB	Output is correct
48	Correct	312 ms	64568 KB	Output is correct
49	Correct	325 ms	64568 KB	Output is correct
50	Correct	413 ms	64568 KB	Output is correct
51	Correct	365 ms	64568 KB	Output is correct
52	Correct	644 ms	256260 KB	Output is correct
53	Correct	637 ms	256260 KB	Output is correct
54	Correct	673 ms	256260 KB	Output is correct
55	Correct	574 ms	256260 KB	Output is correct
56	Correct	519 ms	256260 KB	Output is correct
57	Correct	579 ms	256260 KB	Output is correct
58	Correct	615 ms	256260 KB	Output is correct
59	Correct	580 ms	256260 KB	Output is correct
60	Correct	610 ms	256260 KB	Output is correct
61	Correct	134 ms	256260 KB	Output is correct
62	Correct	649 ms	256260 KB	Output is correct
63	Correct	594 ms	256260 KB	Output is correct
64	Correct	661 ms	256260 KB	Output is correct
65	Correct	616 ms	256260 KB	Output is correct
66	Correct	607 ms	256260 KB	Output is correct
67	Correct	169 ms	256260 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21496 KB	Output is correct
2	Correct	20 ms	21496 KB	Output is correct
3	Correct	22 ms	21540 KB	Output is correct
4	Correct	23 ms	21568 KB	Output is correct
5	Correct	22 ms	21696 KB	Output is correct
6	Correct	25 ms	21728 KB	Output is correct
7	Correct	22 ms	21900 KB	Output is correct
8	Correct	22 ms	21900 KB	Output is correct
9	Correct	23 ms	21952 KB	Output is correct
10	Correct	23 ms	21952 KB	Output is correct
11	Correct	31 ms	21952 KB	Output is correct
12	Correct	27 ms	21952 KB	Output is correct
13	Correct	22 ms	21952 KB	Output is correct
14	Correct	24 ms	21952 KB	Output is correct
15	Correct	22 ms	21952 KB	Output is correct
16	Correct	23 ms	21952 KB	Output is correct
17	Correct	23 ms	21952 KB	Output is correct
18	Correct	28 ms	21952 KB	Output is correct
19	Correct	23 ms	21952 KB	Output is correct
20	Correct	24 ms	21952 KB	Output is correct
21	Correct	22 ms	21952 KB	Output is correct
22	Correct	32 ms	21952 KB	Output is correct
23	Correct	31 ms	21952 KB	Output is correct
24	Correct	23 ms	21952 KB	Output is correct
25	Correct	23 ms	21952 KB	Output is correct
26	Correct	27 ms	21952 KB	Output is correct
27	Correct	27 ms	21952 KB	Output is correct
28	Correct	27 ms	21952 KB	Output is correct
29	Correct	27 ms	21952 KB	Output is correct
30	Correct	29 ms	21952 KB	Output is correct
31	Correct	739 ms	64568 KB	Output is correct
32	Correct	76 ms	64568 KB	Output is correct
33	Correct	691 ms	64568 KB	Output is correct
34	Correct	733 ms	64568 KB	Output is correct
35	Correct	676 ms	64568 KB	Output is correct
36	Correct	644 ms	64568 KB	Output is correct
37	Correct	482 ms	64568 KB	Output is correct
38	Correct	430 ms	64568 KB	Output is correct
39	Correct	382 ms	64568 KB	Output is correct
40	Correct	350 ms	64568 KB	Output is correct
41	Correct	577 ms	64568 KB	Output is correct
42	Correct	615 ms	64568 KB	Output is correct
43	Correct	93 ms	64568 KB	Output is correct
44	Correct	703 ms	64568 KB	Output is correct
45	Correct	658 ms	64568 KB	Output is correct
46	Correct	564 ms	64568 KB	Output is correct
47	Correct	344 ms	64568 KB	Output is correct
48	Correct	312 ms	64568 KB	Output is correct
49	Correct	325 ms	64568 KB	Output is correct
50	Correct	413 ms	64568 KB	Output is correct
51	Correct	365 ms	64568 KB	Output is correct
52	Correct	2734 ms	185112 KB	Output is correct
53	Correct	3644 ms	185112 KB	Output is correct
54	Correct	2891 ms	252748 KB	Output is correct
55	Correct	2782 ms	252748 KB	Output is correct
56	Correct	4645 ms	252748 KB	Output is correct
57	Correct	3861 ms	252748 KB	Output is correct
58	Correct	2768 ms	256260 KB	Output is correct
59	Correct	2652 ms	256260 KB	Output is correct
60	Correct	2761 ms	256260 KB	Output is correct
61	Correct	2881 ms	256260 KB	Output is correct
62	Correct	1987 ms	256260 KB	Output is correct
63	Correct	2104 ms	256260 KB	Output is correct
64	Correct	4644 ms	256260 KB	Output is correct
65	Correct	360 ms	256260 KB	Output is correct
66	Execution timed out	5017 ms	256260 KB	Time limit exceeded
67	Halted	0 ms	0 KB	-

답안 #60890

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