oj.uz

Submission #52226

# Submission time Handle Problem Language Result Execution time Memory
52226 2018-06-25T05:32:01 Z 강한필(#1963) Fortune Telling 2 (JOI14_fortune_telling2) C++11
35 / 100
 2000 ms 112744 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -