답안 #52222 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52222	2018-06-25T05:24:08 Z	강한필(#1963)	운세 보기 2 (JOI14_fortune_telling2)	C++11	35 / 100	2000 ms	75912 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];
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 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]);
        }
        else
            wavelet[rchild[ind]].push_back(wavelet[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::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: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	19 ms	19448 KB	Output is correct
2	Correct	20 ms	19556 KB	Output is correct
3	Correct	29 ms	19608 KB	Output is correct
4	Correct	21 ms	19656 KB	Output is correct
5	Correct	27 ms	19844 KB	Output is correct
6	Correct	27 ms	19872 KB	Output is correct
7	Correct	23 ms	19872 KB	Output is correct
8	Correct	21 ms	19872 KB	Output is correct
9	Correct	23 ms	19872 KB	Output is correct
10	Correct	20 ms	19872 KB	Output is correct
11	Correct	25 ms	19872 KB	Output is correct
12	Correct	24 ms	19872 KB	Output is correct
13	Correct	22 ms	19872 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	19448 KB	Output is correct
2	Correct	20 ms	19556 KB	Output is correct
3	Correct	29 ms	19608 KB	Output is correct
4	Correct	21 ms	19656 KB	Output is correct
5	Correct	27 ms	19844 KB	Output is correct
6	Correct	27 ms	19872 KB	Output is correct
7	Correct	23 ms	19872 KB	Output is correct
8	Correct	21 ms	19872 KB	Output is correct
9	Correct	23 ms	19872 KB	Output is correct
10	Correct	20 ms	19872 KB	Output is correct
11	Correct	25 ms	19872 KB	Output is correct
12	Correct	24 ms	19872 KB	Output is correct
13	Correct	22 ms	19872 KB	Output is correct
14	Correct	99 ms	22224 KB	Output is correct
15	Correct	166 ms	25028 KB	Output is correct
16	Correct	278 ms	27124 KB	Output is correct
17	Correct	392 ms	30948 KB	Output is correct
18	Correct	402 ms	30948 KB	Output is correct
19	Correct	388 ms	30948 KB	Output is correct
20	Correct	430 ms	30948 KB	Output is correct
21	Correct	322 ms	30948 KB	Output is correct
22	Correct	178 ms	30948 KB	Output is correct
23	Correct	190 ms	30948 KB	Output is correct
24	Correct	179 ms	30948 KB	Output is correct
25	Correct	201 ms	30948 KB	Output is correct
26	Correct	307 ms	30948 KB	Output is correct
27	Correct	437 ms	30948 KB	Output is correct
28	Correct	214 ms	30948 KB	Output is correct
29	Correct	455 ms	30948 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	19448 KB	Output is correct
2	Correct	20 ms	19556 KB	Output is correct
3	Correct	29 ms	19608 KB	Output is correct
4	Correct	21 ms	19656 KB	Output is correct
5	Correct	27 ms	19844 KB	Output is correct
6	Correct	27 ms	19872 KB	Output is correct
7	Correct	23 ms	19872 KB	Output is correct
8	Correct	21 ms	19872 KB	Output is correct
9	Correct	23 ms	19872 KB	Output is correct
10	Correct	20 ms	19872 KB	Output is correct
11	Correct	25 ms	19872 KB	Output is correct
12	Correct	24 ms	19872 KB	Output is correct
13	Correct	22 ms	19872 KB	Output is correct
14	Correct	99 ms	22224 KB	Output is correct
15	Correct	166 ms	25028 KB	Output is correct
16	Correct	278 ms	27124 KB	Output is correct
17	Correct	392 ms	30948 KB	Output is correct
18	Correct	402 ms	30948 KB	Output is correct
19	Correct	388 ms	30948 KB	Output is correct
20	Correct	430 ms	30948 KB	Output is correct
21	Correct	322 ms	30948 KB	Output is correct
22	Correct	178 ms	30948 KB	Output is correct
23	Correct	190 ms	30948 KB	Output is correct
24	Correct	179 ms	30948 KB	Output is correct
25	Correct	201 ms	30948 KB	Output is correct
26	Correct	307 ms	30948 KB	Output is correct
27	Correct	437 ms	30948 KB	Output is correct
28	Correct	214 ms	30948 KB	Output is correct
29	Correct	455 ms	30948 KB	Output is correct
30	Correct	421 ms	74496 KB	Output is correct
31	Correct	932 ms	74752 KB	Output is correct
32	Correct	1656 ms	75120 KB	Output is correct
33	Execution timed out	2072 ms	75912 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #52222

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