답안 #52243 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52243	2018-06-25T05:53:23 Z	gs14004	운세 보기 2 (JOI14_fortune_telling2)	C++17	35 / 100	3000 ms	112868 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	27 ms	29176 KB	Output is correct
2	Correct	29 ms	29260 KB	Output is correct
3	Correct	30 ms	29260 KB	Output is correct
4	Correct	29 ms	29260 KB	Output is correct
5	Correct	29 ms	29260 KB	Output is correct
6	Correct	30 ms	29260 KB	Output is correct
7	Correct	30 ms	29260 KB	Output is correct
8	Correct	30 ms	29288 KB	Output is correct
9	Correct	27 ms	29320 KB	Output is correct
10	Correct	27 ms	29320 KB	Output is correct
11	Correct	29 ms	29320 KB	Output is correct
12	Correct	29 ms	29392 KB	Output is correct
13	Correct	30 ms	29400 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	29176 KB	Output is correct
2	Correct	29 ms	29260 KB	Output is correct
3	Correct	30 ms	29260 KB	Output is correct
4	Correct	29 ms	29260 KB	Output is correct
5	Correct	29 ms	29260 KB	Output is correct
6	Correct	30 ms	29260 KB	Output is correct
7	Correct	30 ms	29260 KB	Output is correct
8	Correct	30 ms	29288 KB	Output is correct
9	Correct	27 ms	29320 KB	Output is correct
10	Correct	27 ms	29320 KB	Output is correct
11	Correct	29 ms	29320 KB	Output is correct
12	Correct	29 ms	29392 KB	Output is correct
13	Correct	30 ms	29400 KB	Output is correct
14	Correct	92 ms	32984 KB	Output is correct
15	Correct	185 ms	37160 KB	Output is correct
16	Correct	280 ms	40276 KB	Output is correct
17	Correct	405 ms	45672 KB	Output is correct
18	Correct	414 ms	45800 KB	Output is correct
19	Correct	387 ms	45800 KB	Output is correct
20	Correct	420 ms	45800 KB	Output is correct
21	Correct	324 ms	45844 KB	Output is correct
22	Correct	202 ms	45844 KB	Output is correct
23	Correct	204 ms	45844 KB	Output is correct
24	Correct	205 ms	45844 KB	Output is correct
25	Correct	202 ms	45844 KB	Output is correct
26	Correct	330 ms	45844 KB	Output is correct
27	Correct	442 ms	45844 KB	Output is correct
28	Correct	226 ms	45844 KB	Output is correct
29	Correct	526 ms	45844 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	29176 KB	Output is correct
2	Correct	29 ms	29260 KB	Output is correct
3	Correct	30 ms	29260 KB	Output is correct
4	Correct	29 ms	29260 KB	Output is correct
5	Correct	29 ms	29260 KB	Output is correct
6	Correct	30 ms	29260 KB	Output is correct
7	Correct	30 ms	29260 KB	Output is correct
8	Correct	30 ms	29288 KB	Output is correct
9	Correct	27 ms	29320 KB	Output is correct
10	Correct	27 ms	29320 KB	Output is correct
11	Correct	29 ms	29320 KB	Output is correct
12	Correct	29 ms	29392 KB	Output is correct
13	Correct	30 ms	29400 KB	Output is correct
14	Correct	92 ms	32984 KB	Output is correct
15	Correct	185 ms	37160 KB	Output is correct
16	Correct	280 ms	40276 KB	Output is correct
17	Correct	405 ms	45672 KB	Output is correct
18	Correct	414 ms	45800 KB	Output is correct
19	Correct	387 ms	45800 KB	Output is correct
20	Correct	420 ms	45800 KB	Output is correct
21	Correct	324 ms	45844 KB	Output is correct
22	Correct	202 ms	45844 KB	Output is correct
23	Correct	204 ms	45844 KB	Output is correct
24	Correct	205 ms	45844 KB	Output is correct
25	Correct	202 ms	45844 KB	Output is correct
26	Correct	330 ms	45844 KB	Output is correct
27	Correct	442 ms	45844 KB	Output is correct
28	Correct	226 ms	45844 KB	Output is correct
29	Correct	526 ms	45844 KB	Output is correct
30	Correct	557 ms	111308 KB	Output is correct
31	Correct	1087 ms	111660 KB	Output is correct
32	Correct	1716 ms	112232 KB	Output is correct
33	Execution timed out	3058 ms	112868 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #52243

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