답안 #52226 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52226	2018-06-25T05:32:01 Z	강한필(#1963)	운세 보기 2 (JOI14_fortune_telling2)	C++11	35 / 100	2000 ms	112744 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]));
}

int find_inside(int from, int to)
{
    int N = wavelet[0].size();
    int lo = -1; //here must be answer
    int hi = N; //here mustn't be answer;
    while(lo+1!=hi)
    {
        int mi = (lo+hi)/2;
        int cntl = count_ge(mi, N-1, to+1, 0);
        int cntr = count_ge(mi, N-1, from, 0);
        //printf("%d %d %d [%d, %d]\n", mi, cntl, cntr, from, to);
        if(cntl != cntr) lo = mi;
        else hi = mi;
    }
    return lo;
}

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);
        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:127: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:129: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:133: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	29 ms	29048 KB	Output is correct
2	Correct	29 ms	29156 KB	Output is correct
3	Correct	31 ms	29232 KB	Output is correct
4	Correct	31 ms	29280 KB	Output is correct
5	Correct	31 ms	29280 KB	Output is correct
6	Correct	33 ms	29284 KB	Output is correct
7	Correct	31 ms	29312 KB	Output is correct
8	Correct	30 ms	29336 KB	Output is correct
9	Correct	30 ms	29336 KB	Output is correct
10	Correct	32 ms	29336 KB	Output is correct
11	Correct	33 ms	29336 KB	Output is correct
12	Correct	36 ms	29336 KB	Output is correct
13	Correct	38 ms	29496 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	29048 KB	Output is correct
2	Correct	29 ms	29156 KB	Output is correct
3	Correct	31 ms	29232 KB	Output is correct
4	Correct	31 ms	29280 KB	Output is correct
5	Correct	31 ms	29280 KB	Output is correct
6	Correct	33 ms	29284 KB	Output is correct
7	Correct	31 ms	29312 KB	Output is correct
8	Correct	30 ms	29336 KB	Output is correct
9	Correct	30 ms	29336 KB	Output is correct
10	Correct	32 ms	29336 KB	Output is correct
11	Correct	33 ms	29336 KB	Output is correct
12	Correct	36 ms	29336 KB	Output is correct
13	Correct	38 ms	29496 KB	Output is correct
14	Correct	109 ms	32828 KB	Output is correct
15	Correct	193 ms	37040 KB	Output is correct
16	Correct	290 ms	40124 KB	Output is correct
17	Correct	408 ms	45804 KB	Output is correct
18	Correct	424 ms	45804 KB	Output is correct
19	Correct	420 ms	45804 KB	Output is correct
20	Correct	484 ms	45804 KB	Output is correct
21	Correct	344 ms	45804 KB	Output is correct
22	Correct	227 ms	45804 KB	Output is correct
23	Correct	204 ms	45804 KB	Output is correct
24	Correct	217 ms	45804 KB	Output is correct
25	Correct	209 ms	45804 KB	Output is correct
26	Correct	337 ms	45804 KB	Output is correct
27	Correct	458 ms	45804 KB	Output is correct
28	Correct	239 ms	45804 KB	Output is correct
29	Correct	496 ms	45804 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	29048 KB	Output is correct
2	Correct	29 ms	29156 KB	Output is correct
3	Correct	31 ms	29232 KB	Output is correct
4	Correct	31 ms	29280 KB	Output is correct
5	Correct	31 ms	29280 KB	Output is correct
6	Correct	33 ms	29284 KB	Output is correct
7	Correct	31 ms	29312 KB	Output is correct
8	Correct	30 ms	29336 KB	Output is correct
9	Correct	30 ms	29336 KB	Output is correct
10	Correct	32 ms	29336 KB	Output is correct
11	Correct	33 ms	29336 KB	Output is correct
12	Correct	36 ms	29336 KB	Output is correct
13	Correct	38 ms	29496 KB	Output is correct
14	Correct	109 ms	32828 KB	Output is correct
15	Correct	193 ms	37040 KB	Output is correct
16	Correct	290 ms	40124 KB	Output is correct
17	Correct	408 ms	45804 KB	Output is correct
18	Correct	424 ms	45804 KB	Output is correct
19	Correct	420 ms	45804 KB	Output is correct
20	Correct	484 ms	45804 KB	Output is correct
21	Correct	344 ms	45804 KB	Output is correct
22	Correct	227 ms	45804 KB	Output is correct
23	Correct	204 ms	45804 KB	Output is correct
24	Correct	217 ms	45804 KB	Output is correct
25	Correct	209 ms	45804 KB	Output is correct
26	Correct	337 ms	45804 KB	Output is correct
27	Correct	458 ms	45804 KB	Output is correct
28	Correct	239 ms	45804 KB	Output is correct
29	Correct	496 ms	45804 KB	Output is correct
30	Correct	502 ms	111260 KB	Output is correct
31	Correct	1040 ms	111648 KB	Output is correct
32	Correct	1689 ms	112368 KB	Output is correct
33	Execution timed out	2088 ms	112744 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #52226

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
0 / 65.0