답안 #67310 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67310	2018-08-13T22:02:13 Z	duality	운세 보기 2 (JOI14_fortune_telling2)	C++11	100 / 100	393 ms	120592 KB

fortune_telling2

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

// 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(),

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6

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

struct card { int a,b,f; };
bool comp(card a,card b) {
    return a.b > b.b;
}
card C[200000];
pii T[200000];
int tree[1 << 19];
int tree2[200001];
int build(int s,int e,int i) {
    if (s == e) {
        tree[i] = T[s].second;
        return tree[i];
    }

    int mid = (s+e) / 2;
    tree[i] = max(build(s,mid,2*i+1),build(mid+1,e,2*i+2));
    return tree[i];
}
int query(int s,int e,int qs,int qe,int i) {
    if ((s > qe) || (e < qs)) return -1;
    else if ((s >= qs) && (e <= qe)) return tree[i];

    int mid = (s+e) / 2;
    return max(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2));
}
int query2(int i) {
    int sum = 0;
    for (i++; i > 0; i -= i & (-i)) sum += tree2[i];
    return sum;
}
int query2(int s,int e) {
    return query2(e) - query2(s-1);
}
int update2(int i,int num,int K) {
    for (i++; i <= K; i += i & (-i)) tree2[i] += num;
    return 0;
}
int main() {
    int i;
    int N,K;
    scanf("%d %d",&N,&K);
    for (i = 0; i < N; i++) {
        scanf("%d %d",&C[i].a,&C[i].b);
        if (C[i].a > C[i].b) swap(C[i].a,C[i].b),C[i].f = 1;
    }
    for (i = 0; i < K; i++) scanf("%d",&T[i].first),T[i].second = i;

    LLI sum = 0;
    int e = K-1;
    sort(C,C+N,comp);
    sort(T,T+K);
    build(0,K-1,0);
    for (i = 0; i < N; i++) {
        int s = lower_bound(T,T+K,make_pair(C[i].a,0))-T;
        while ((e >= 0) && (C[i].b <= T[e].first)) update2(T[e].second,1,K),e--;
        int l = query(0,K-1,s,e,0);
        if (l == -1) sum += (((K-s) & 1)^C[i].f) ? C[i].b:C[i].a;
        else sum += (query2(l,K-1) & 1) ? C[i].a:C[i].b;
    }
    printf("%lld\n",sum);

    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&K);
     ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&C[i].a,&C[i].b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:89:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < K; i++) scanf("%d",&T[i].first),T[i].second = i;
                             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	560 KB	Output is correct
3	Correct	4 ms	644 KB	Output is correct
4	Correct	4 ms	884 KB	Output is correct
5	Correct	3 ms	884 KB	Output is correct
6	Correct	4 ms	884 KB	Output is correct
7	Correct	3 ms	884 KB	Output is correct
8	Correct	3 ms	988 KB	Output is correct
9	Correct	3 ms	988 KB	Output is correct
10	Correct	3 ms	988 KB	Output is correct
11	Correct	3 ms	988 KB	Output is correct
12	Correct	3 ms	1024 KB	Output is correct
13	Correct	4 ms	1052 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	560 KB	Output is correct
3	Correct	4 ms	644 KB	Output is correct
4	Correct	4 ms	884 KB	Output is correct
5	Correct	3 ms	884 KB	Output is correct
6	Correct	4 ms	884 KB	Output is correct
7	Correct	3 ms	884 KB	Output is correct
8	Correct	3 ms	988 KB	Output is correct
9	Correct	3 ms	988 KB	Output is correct
10	Correct	3 ms	988 KB	Output is correct
11	Correct	3 ms	988 KB	Output is correct
12	Correct	3 ms	1024 KB	Output is correct
13	Correct	4 ms	1052 KB	Output is correct
14	Correct	16 ms	1776 KB	Output is correct
15	Correct	31 ms	2708 KB	Output is correct
16	Correct	47 ms	3800 KB	Output is correct
17	Correct	60 ms	5440 KB	Output is correct
18	Correct	62 ms	6592 KB	Output is correct
19	Correct	56 ms	7760 KB	Output is correct
20	Correct	53 ms	8932 KB	Output is correct
21	Correct	59 ms	10208 KB	Output is correct
22	Correct	43 ms	10816 KB	Output is correct
23	Correct	40 ms	11400 KB	Output is correct
24	Correct	46 ms	12196 KB	Output is correct
25	Correct	36 ms	12916 KB	Output is correct
26	Correct	40 ms	13904 KB	Output is correct
27	Correct	41 ms	15076 KB	Output is correct
28	Correct	42 ms	16240 KB	Output is correct
29	Correct	40 ms	17352 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	560 KB	Output is correct
3	Correct	4 ms	644 KB	Output is correct
4	Correct	4 ms	884 KB	Output is correct
5	Correct	3 ms	884 KB	Output is correct
6	Correct	4 ms	884 KB	Output is correct
7	Correct	3 ms	884 KB	Output is correct
8	Correct	3 ms	988 KB	Output is correct
9	Correct	3 ms	988 KB	Output is correct
10	Correct	3 ms	988 KB	Output is correct
11	Correct	3 ms	988 KB	Output is correct
12	Correct	3 ms	1024 KB	Output is correct
13	Correct	4 ms	1052 KB	Output is correct
14	Correct	16 ms	1776 KB	Output is correct
15	Correct	31 ms	2708 KB	Output is correct
16	Correct	47 ms	3800 KB	Output is correct
17	Correct	60 ms	5440 KB	Output is correct
18	Correct	62 ms	6592 KB	Output is correct
19	Correct	56 ms	7760 KB	Output is correct
20	Correct	53 ms	8932 KB	Output is correct
21	Correct	59 ms	10208 KB	Output is correct
22	Correct	43 ms	10816 KB	Output is correct
23	Correct	40 ms	11400 KB	Output is correct
24	Correct	46 ms	12196 KB	Output is correct
25	Correct	36 ms	12916 KB	Output is correct
26	Correct	40 ms	13904 KB	Output is correct
27	Correct	41 ms	15076 KB	Output is correct
28	Correct	42 ms	16240 KB	Output is correct
29	Correct	40 ms	17352 KB	Output is correct
30	Correct	88 ms	22636 KB	Output is correct
31	Correct	128 ms	26044 KB	Output is correct
32	Correct	186 ms	30624 KB	Output is correct
33	Correct	393 ms	37576 KB	Output is correct
34	Correct	78 ms	37576 KB	Output is correct
35	Correct	336 ms	45316 KB	Output is correct
36	Correct	382 ms	51120 KB	Output is correct
37	Correct	346 ms	56928 KB	Output is correct
38	Correct	283 ms	62732 KB	Output is correct
39	Correct	294 ms	68696 KB	Output is correct
40	Correct	274 ms	74248 KB	Output is correct
41	Correct	289 ms	80096 KB	Output is correct
42	Correct	262 ms	85964 KB	Output is correct
43	Correct	206 ms	90516 KB	Output is correct
44	Correct	194 ms	95780 KB	Output is correct
45	Correct	178 ms	101040 KB	Output is correct
46	Correct	220 ms	105016 KB	Output is correct
47	Correct	208 ms	108904 KB	Output is correct
48	Correct	216 ms	114776 KB	Output is correct
49	Correct	250 ms	120592 KB	Output is correct

답안 #67310

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0