답안 #52227 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52227	2018-06-25T05:33:06 Z	강한필(#1963)	운세 보기 2 (JOI14_fortune_telling2)	C++11	100 / 100	978 ms	113064 KB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 202020;

namespace wavelet
{
vector<int> wavelet[2*MAXN];
vector<int> leftind[2*MAXN];
vector<int> orig[2*MAXN];
int minv[2*MAXN];
int maxv[2*MAXN];
int lchild[2*MAXN];
int rchild[2*MAXN];
int gind = 0;

inline int lchildind(int ind, int x)
{
    return leftind[ind][x]-1;
}
inline int rchildind(int ind, int x)
{
    return x-leftind[ind][x];
}

int count_ge(int from, int to, int K, int ind)
{
    //printf("=%d %d %d %d\n", from, to, K, ind);
    if(from > to) return 0;
    if(maxv[ind] < K) return 0;
    if(minv[ind] >= K) return to-from+1;
    
    int ls, rs, le, re;
    if(wavelet[ind][from] <= (maxv[ind]+minv[ind])/2)
    {
        ls = leftind[ind][from]-1;
        rs = from-ls;
    }
    else
    {
        ls = leftind[ind][from];
        rs = from-ls;
    }
    
    if(wavelet[ind][to] <= (maxv[ind]+minv[ind])/2)
    {
        le = leftind[ind][to]-1;
        re = to-1-le;
    }
    else
    {
        le = leftind[ind][to]-1;
        re = to-1-le;
    }
    
    return count_ge(ls, le, K, lchild[ind])
         + count_ge(rs, re, K, rchild[ind]);
}

int find_inside(int from, int to, int ind)
{
    if(from > to) return -1;
    if(to < minv[ind]) return -1;
    if(maxv[ind] < from) return -1;
    
    if(from <= minv[ind] && maxv[ind] <= to)
        return orig[ind].back();

    return max(find_inside(from, to, lchild[ind]), find_inside(from, to, rchild[ind]));
}

void build_wavelet(int ind)
{
    int N = wavelet[ind].size();
    minv[ind] = *min_element(wavelet[ind].begin(), wavelet[ind].end());
    maxv[ind] = *max_element(wavelet[ind].begin(), wavelet[ind].end());
    if(minv[ind] == maxv[ind]) return;
    lchild[ind] = gind++;
    rchild[ind] = gind++;
    int midv = (minv[ind]+maxv[ind])/2;
    //minv[ind] ~ midv, midv+1, maxv[ind]
    int p = 0;
    for(int i=0; i<N; ++i)
    {
        if(wavelet[ind][i] <= midv)
        {
            ++p;
            wavelet[lchild[ind]].push_back(wavelet[ind][i]);
            orig[lchild[ind]].push_back(orig[ind][i]);
        }
        else
        {
            wavelet[rchild[ind]].push_back(wavelet[ind][i]);
            orig[rchild[ind]].push_back(orig[ind][i]);
        }
        leftind[ind].push_back(p);
    }
    build_wavelet(lchild[ind]);
    build_wavelet(rchild[ind]);
}


};

int N, K;
int A[MAXN];
int B[MAXN];
int T[MAXN];
int main()
{
    scanf("%d%d", &N, &K);
    for(int i=0; i<N; ++i)
        scanf("%d%d", A+i, B+i);
    
    for(int i=0; i<K; ++i)
    {
        int t; scanf("%d", &t);
        wavelet::wavelet[wavelet::gind].push_back(t);
        wavelet::orig[wavelet::gind].push_back(i);
    }
    wavelet::build_wavelet(wavelet::gind++);
 
  
    long long ans = 0;
    for(int i=0; i<N; ++i)
    {
        int small = min(A[i], B[i]);
        int large = max(A[i], B[i]);
        int ind = wavelet::find_inside(small, large-1, 0);
        int now = A[i];
        if(ind != -1) now = large;
        int cnt = wavelet::count_ge(ind+1, K-1, large, 0);
        if(cnt&1) now = small+large-now;
        ans += now;
        //printf("%d %d %d\n", ind, cnt, now);
    }
    printf("%lld\n", ans);
    
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:110: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:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", A+i, B+i);
         ~~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:116:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t; scanf("%d", &t);
                ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	29048 KB	Output is correct
2	Correct	34 ms	29156 KB	Output is correct
3	Correct	28 ms	29232 KB	Output is correct
4	Correct	29 ms	29360 KB	Output is correct
5	Correct	29 ms	29360 KB	Output is correct
6	Correct	28 ms	29360 KB	Output is correct
7	Correct	28 ms	29360 KB	Output is correct
8	Correct	28 ms	29360 KB	Output is correct
9	Correct	38 ms	29360 KB	Output is correct
10	Correct	34 ms	29360 KB	Output is correct
11	Correct	36 ms	29360 KB	Output is correct
12	Correct	28 ms	29360 KB	Output is correct
13	Correct	33 ms	29420 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	29048 KB	Output is correct
2	Correct	34 ms	29156 KB	Output is correct
3	Correct	28 ms	29232 KB	Output is correct
4	Correct	29 ms	29360 KB	Output is correct
5	Correct	29 ms	29360 KB	Output is correct
6	Correct	28 ms	29360 KB	Output is correct
7	Correct	28 ms	29360 KB	Output is correct
8	Correct	28 ms	29360 KB	Output is correct
9	Correct	38 ms	29360 KB	Output is correct
10	Correct	34 ms	29360 KB	Output is correct
11	Correct	36 ms	29360 KB	Output is correct
12	Correct	28 ms	29360 KB	Output is correct
13	Correct	33 ms	29420 KB	Output is correct
14	Correct	58 ms	32876 KB	Output is correct
15	Correct	93 ms	37180 KB	Output is correct
16	Correct	118 ms	40172 KB	Output is correct
17	Correct	163 ms	45676 KB	Output is correct
18	Correct	154 ms	45676 KB	Output is correct
19	Correct	159 ms	45676 KB	Output is correct
20	Correct	199 ms	45852 KB	Output is correct
21	Correct	150 ms	45852 KB	Output is correct
22	Correct	110 ms	45852 KB	Output is correct
23	Correct	110 ms	45852 KB	Output is correct
24	Correct	111 ms	45852 KB	Output is correct
25	Correct	111 ms	45852 KB	Output is correct
26	Correct	127 ms	45852 KB	Output is correct
27	Correct	179 ms	45852 KB	Output is correct
28	Correct	138 ms	45872 KB	Output is correct
29	Correct	199 ms	45872 KB	Output is correct

Subtask #3
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	29048 KB	Output is correct
2	Correct	34 ms	29156 KB	Output is correct
3	Correct	28 ms	29232 KB	Output is correct
4	Correct	29 ms	29360 KB	Output is correct
5	Correct	29 ms	29360 KB	Output is correct
6	Correct	28 ms	29360 KB	Output is correct
7	Correct	28 ms	29360 KB	Output is correct
8	Correct	28 ms	29360 KB	Output is correct
9	Correct	38 ms	29360 KB	Output is correct
10	Correct	34 ms	29360 KB	Output is correct
11	Correct	36 ms	29360 KB	Output is correct
12	Correct	28 ms	29360 KB	Output is correct
13	Correct	33 ms	29420 KB	Output is correct
14	Correct	58 ms	32876 KB	Output is correct
15	Correct	93 ms	37180 KB	Output is correct
16	Correct	118 ms	40172 KB	Output is correct
17	Correct	163 ms	45676 KB	Output is correct
18	Correct	154 ms	45676 KB	Output is correct
19	Correct	159 ms	45676 KB	Output is correct
20	Correct	199 ms	45852 KB	Output is correct
21	Correct	150 ms	45852 KB	Output is correct
22	Correct	110 ms	45852 KB	Output is correct
23	Correct	110 ms	45852 KB	Output is correct
24	Correct	111 ms	45852 KB	Output is correct
25	Correct	111 ms	45852 KB	Output is correct
26	Correct	127 ms	45852 KB	Output is correct
27	Correct	179 ms	45852 KB	Output is correct
28	Correct	138 ms	45872 KB	Output is correct
29	Correct	199 ms	45872 KB	Output is correct
30	Correct	397 ms	111360 KB	Output is correct
31	Correct	547 ms	111848 KB	Output is correct
32	Correct	618 ms	112232 KB	Output is correct
33	Correct	893 ms	113004 KB	Output is correct
34	Correct	400 ms	113004 KB	Output is correct
35	Correct	925 ms	113004 KB	Output is correct
36	Correct	978 ms	113004 KB	Output is correct
37	Correct	920 ms	113004 KB	Output is correct
38	Correct	928 ms	113004 KB	Output is correct
39	Correct	917 ms	113004 KB	Output is correct
40	Correct	716 ms	113004 KB	Output is correct
41	Correct	844 ms	113004 KB	Output is correct
42	Correct	903 ms	113024 KB	Output is correct
43	Correct	499 ms	113064 KB	Output is correct
44	Correct	463 ms	113064 KB	Output is correct
45	Correct	453 ms	113064 KB	Output is correct
46	Correct	476 ms	113064 KB	Output is correct
47	Correct	449 ms	113064 KB	Output is correct
48	Correct	783 ms	113064 KB	Output is correct
49	Correct	759 ms	113064 KB	Output is correct

답안 #52227

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