답안 #54582 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54582	2018-07-04T06:54:45 Z	ikura355	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	1966 ms	148516 KB

fortune_telling2

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

const int maxn = 2e5 + 5;

int n,m;
int a[maxn], b[maxn], c[maxn];
int pos[maxn], res[maxn];
vector<int> p[maxn];

int sz;
int limit, tree[maxn*9];
int fen[maxn*3];

map<int,int> mp;
int rec[maxn*3];

void cpidx() {
    for(int i=1;i<=n;i++) mp[a[i]], mp[b[i]];
    for(int i=1;i<=m;i++) mp[c[i]];
    for(auto &it : mp) {
        it.second = ++sz;
        rec[sz] = it.first;
    }
    for(int i=1;i<=n;i++) a[i] = mp[a[i]], b[i] = mp[b[i]];
    for(int i=1;i<=m;i++) c[i] = mp[c[i]];
}
void init() {
    limit = 1;
    while(limit<=sz) limit*=2;
}
void update(int x, int val) {
    x += limit;
    tree[x] = max(tree[x], val);
    while(x) {
        x/=2;
        tree[x] = max(tree[x<<1], tree[x<<1|1]);
    }
}
int query(int l, int r) {
    l += limit; r += limit;
    int res = 0;
    while(l<r) {
        if(l%2!=0) res = max(res, tree[l++]);
        if(r%2==0) res = max(res, tree[r--]);
        l/=2; r/=2;
    }
    if(l==r) res = max(res, tree[l]);
    return res;
}
void add(int x, int val) {
    while(x) {
        fen[x] += val;
        x -= x&-x;
    }
}
int sum(int x) {
    int res = 0;
    while(x<=sz) {
        res += fen[x];
        x += x&-x;
    }
    return res;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    for(int i=1;i<=m;i++) scanf("%d",&c[i]);
    cpidx();
    init();
    for(int i=1;i<=m;i++) update(c[i], i);
    for(int i=1;i<=n;i++) {
        pos[i] = query(min(a[i],b[i]), max(a[i],b[i])-1);
        p[pos[i]+1].push_back(i);
    }
    for(int i=m;i>=1;i--) {
        add(c[i],1);
        for(auto x : p[i]) res[x] = sum(max(a[x], b[x]));
    }
    long long ans = 0;
    for(int i=1;i<=n;i++) {
//        printf("%d : pos = %d res = %d\n",i,pos[i],res[i]);
        if(pos[i]==0) {
            if(res[i]%2==0) ans += rec[a[i]];//, printf("%d ",rec[a[i]]);
            else ans += rec[b[i]];//, printf("%d ",rec[b[i]]);
        }
        else {
            if(res[i]%2==1) ans += rec[min(a[i], b[i])];//, printf("%d ",rec[min(a[i], b[i])]);
            else ans += rec[max(a[i], b[i])];//, printf("%d ",rec[max(a[i], b[i])]);
        }
    }
    printf("%lld",ans);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:67:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:68:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=m;i++) scanf("%d",&c[i]);
                           ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	9 ms	5348 KB	Output is correct
3	Correct	8 ms	5440 KB	Output is correct
4	Correct	8 ms	5580 KB	Output is correct
5	Correct	10 ms	5628 KB	Output is correct
6	Correct	8 ms	5628 KB	Output is correct
7	Correct	9 ms	5636 KB	Output is correct
8	Correct	8 ms	5660 KB	Output is correct
9	Correct	7 ms	5824 KB	Output is correct
10	Correct	7 ms	5824 KB	Output is correct
11	Correct	7 ms	5824 KB	Output is correct
12	Correct	7 ms	5824 KB	Output is correct
13	Correct	8 ms	6024 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	9 ms	5348 KB	Output is correct
3	Correct	8 ms	5440 KB	Output is correct
4	Correct	8 ms	5580 KB	Output is correct
5	Correct	10 ms	5628 KB	Output is correct
6	Correct	8 ms	5628 KB	Output is correct
7	Correct	9 ms	5636 KB	Output is correct
8	Correct	8 ms	5660 KB	Output is correct
9	Correct	7 ms	5824 KB	Output is correct
10	Correct	7 ms	5824 KB	Output is correct
11	Correct	7 ms	5824 KB	Output is correct
12	Correct	7 ms	5824 KB	Output is correct
13	Correct	8 ms	6024 KB	Output is correct
14	Correct	35 ms	8292 KB	Output is correct
15	Correct	76 ms	10992 KB	Output is correct
16	Correct	128 ms	14112 KB	Output is correct
17	Correct	176 ms	17340 KB	Output is correct
18	Correct	168 ms	18492 KB	Output is correct
19	Correct	166 ms	19584 KB	Output is correct
20	Correct	175 ms	20928 KB	Output is correct
21	Correct	163 ms	22012 KB	Output is correct
22	Correct	112 ms	22012 KB	Output is correct
23	Correct	88 ms	22012 KB	Output is correct
24	Correct	81 ms	22012 KB	Output is correct
25	Correct	113 ms	22792 KB	Output is correct
26	Correct	102 ms	22792 KB	Output is correct
27	Correct	125 ms	24520 KB	Output is correct
28	Correct	116 ms	25560 KB	Output is correct
29	Correct	138 ms	28168 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	9 ms	5348 KB	Output is correct
3	Correct	8 ms	5440 KB	Output is correct
4	Correct	8 ms	5580 KB	Output is correct
5	Correct	10 ms	5628 KB	Output is correct
6	Correct	8 ms	5628 KB	Output is correct
7	Correct	9 ms	5636 KB	Output is correct
8	Correct	8 ms	5660 KB	Output is correct
9	Correct	7 ms	5824 KB	Output is correct
10	Correct	7 ms	5824 KB	Output is correct
11	Correct	7 ms	5824 KB	Output is correct
12	Correct	7 ms	5824 KB	Output is correct
13	Correct	8 ms	6024 KB	Output is correct
14	Correct	35 ms	8292 KB	Output is correct
15	Correct	76 ms	10992 KB	Output is correct
16	Correct	128 ms	14112 KB	Output is correct
17	Correct	176 ms	17340 KB	Output is correct
18	Correct	168 ms	18492 KB	Output is correct
19	Correct	166 ms	19584 KB	Output is correct
20	Correct	175 ms	20928 KB	Output is correct
21	Correct	163 ms	22012 KB	Output is correct
22	Correct	112 ms	22012 KB	Output is correct
23	Correct	88 ms	22012 KB	Output is correct
24	Correct	81 ms	22012 KB	Output is correct
25	Correct	113 ms	22792 KB	Output is correct
26	Correct	102 ms	22792 KB	Output is correct
27	Correct	125 ms	24520 KB	Output is correct
28	Correct	116 ms	25560 KB	Output is correct
29	Correct	138 ms	28168 KB	Output is correct
30	Correct	424 ms	37676 KB	Output is correct
31	Correct	659 ms	46628 KB	Output is correct
32	Correct	1039 ms	57568 KB	Output is correct
33	Correct	1843 ms	78032 KB	Output is correct
34	Correct	367 ms	78032 KB	Output is correct
35	Correct	1723 ms	85740 KB	Output is correct
36	Correct	1716 ms	91488 KB	Output is correct
37	Correct	1738 ms	97408 KB	Output is correct
38	Correct	1966 ms	103400 KB	Output is correct
39	Correct	1705 ms	109092 KB	Output is correct
40	Correct	1465 ms	113792 KB	Output is correct
41	Correct	1675 ms	120520 KB	Output is correct
42	Correct	1582 ms	126356 KB	Output is correct
43	Correct	780 ms	127868 KB	Output is correct
44	Correct	807 ms	133588 KB	Output is correct
45	Correct	795 ms	139968 KB	Output is correct
46	Correct	683 ms	139968 KB	Output is correct
47	Correct	690 ms	139968 KB	Output is correct
48	Correct	1080 ms	142696 KB	Output is correct
49	Correct	997 ms	148516 KB	Output is correct

답안 #54582

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